pic

Container With Most Water 

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

分析

题意是：给出一个整形数组a1，a2...，an，数组的每个元素表示一个坐标(i, ai)。对每个坐标(i, ai)和(i, 0)，连接一条线，n个元素就有n条线，再加上X坐标轴构成了一个容器。要求找到两条竖线，使之和X轴构成的小容器能够容纳最多的水。

要理解题意，必须先意识到水的特点是总是保持一个矩形，以最小的height那条边作为矩形的高。 

     * 这是一道双指针/滑动窗口的题型，即利用两个指针对一个数组或链表进行扫描。
     * 扫描方式有以不同速度从头向尾扫描，或者分别从头和尾向中间扫描。
     * 这道题最简单的做法是用第一种扫描方式，两层for循环，复杂度O(N^2),但是leetcode判断超时；
     * AC的解法使用了分别从头和尾向中间扫描的方式，复杂度为O(N),需要注意的是判断终止条件。

    编程实现两种复杂度的算法：O(N*N)和O(N)

Code

Code 1:O(N*N)算法(Time Limit Exceeded)

class Solution {
public:
    /* 
     * 因为水的特性，在容器里总是以矩形存在的，所以最小的height才是高
     * 最简单的方法是设置两层for循环，枚举所有的左边height和右边height，求出所有面积，得出最大面积。
     * 这个算法复杂度O(N^2)，leetcode平台判断为Time Limit Exceeded超时。
     * */
    int maxArea(vector<int> &height) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(height.size() < 2)
        	return 0;
        int maxArea = 0;
        int tempArea = 0;
        for(int left = 0; left < height.size() - 1; left++)
        {
        	for(int right = left + 1; right < height.size(); right++)
        	{
        		tempArea =std::min(height[left], height[right]) * (right - left);
        		if(tempArea > maxArea)
        			maxArea = tempArea;
        	}
        }
        return maxArea;
    }
};

Code 2:O(N)算法(Accepted)

class Solution {
public:
    /* 
     * 这是一道双指针/滑动窗口的题型，即利用两个指针对一个数组或链表进行扫描。
     * 扫描方式有以不同速度从头向尾扫描，或者分别从头和尾向中间扫描。
     * 这道题最简单的做法是用第一种扫描方式，两层for循环，复杂度O(N^2),但是leetcode判断超时；
     * 下面的解法使用了分别从头和尾向中间扫描的方式，复杂度为O(N),需要注意的是判断终止条件。
     *
     * */
    int maxArea(vector<int> &height) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
    	if(height.size() < 2)
    		return 0;
    	int maxArea = 0; 
    	int tempArea = 0;
    	int left = 0, right = height.size() - 1;
    	while( left < right)
    	{
            //水的特点是总是保持一个矩形，以最小的height那条边作为矩形的高
    		tempArea = (right - left)*std::min(height[left], height[right]);
    		maxArea = std::max(tempArea, maxArea);

            //这是整段代码的关键点，指针的移动条件
    		if(height[left] <= height[right])
    			left++;
    		else
    			right--;
    	}
    	return maxArea;
    }
};

pic