011 - Container With Most Water

Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.
Hide Tags
Array Two Pointers
Hide Similar Problems
(H) Trapping Rain Water
 
起先看错题了，以为是Trapping Rain Water，折腾了一通发现期待的输出不是那么回事，汗。
而后写了一个简单粗暴的，弄个buffer，不断更新每个起点能获得的最大面积（水量），但复杂度是O(n²)妥妥地超时了。
想来想去，最大面积无外乎长乘宽，也就是短的line的长度乘以两个line之间的距离，那就是怎么选长和宽了。
看起来似乎两头逼近似乎可行，试着写了一个，从两头开始，将小的一个向中间移动，直到遇到line长度更大的，
然后另一头就变成小的了，再移动它，不断逼近，并计算每次的面积，从中找到最大值，果然一举搞定，24 ms。
 
class Solution {
public:
    int maxArea(vector<int>& height) {
        int sz=height.size();
        int rst=0;
        if(sz>1)
        {
            int idx1=0, idx2=sz-1, idx=0;
           
            while(idx1 < idx2)
            {
                int low = min(height[idx1], height[idx2]);
                int num = low*(idx2-idx1);
                if(num>rst)
                    rst = num;
               
                if(low == height[idx1])
                    while(idx1<idx2 && height[idx1]<=low)
                        idx1++;
                else
                    while(idx2>idx1 && height[idx2]<=low)
                        idx2--;
            }
        }
        return rst;
    }

    int maxArea_timeout(vector<int>& height) {
        int sz=height.size();
        int rst=0;
        if(sz>1)
        {
            int zz=sz-1, sum=0, idx1=0, idx2=0, idx=0, peak1=0, peak2=0;
           
            int buf[zz]={0}; //to store max water start from line i
           
            for(int ii=1; ii<sz; ++ii)
            {
                buf[ii-1] = 0;
                for(int bb=0; bb<ii; ++bb)
                {
                    int low = min(height[bb], height[ii]);
                    buf[bb] = max(buf[bb], low*(ii-bb));
                    if(rst<buf[bb])
                        rst = buf[bb];
                }
            }
           
        }           
        return rst;
    }
};
24 ms.