GroupBlog

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.

题意：
给于一个序列，序列里面的数字代表高度，数字下标之差作为底边，两个高度之间能当作容器装水且装水量取决与两者较低值和两者在序列中的下标之差。

思路：
1.最普通的暴力求解法，但是测试时显示超时了，O(n^2)
2.类似贪心的算法，取左边界和右边界，计算，然后每次选取较低的高度的下标推进，从而保留高的下标记，保证下一次我们可能选取到较优的解。比如，cont = min(a[i]，a[j])*(j-i) and i < j，如果a[i] < a[j]，那么=>i++，因为i++和j--容器底边都是减1，而我们保留高度高的a[j]，下一次计算时肯定会比执行j--的容量大。也就是每次尽量向更优的解去移动，至于有些没移动到的范围是因为我们在判断时（如上面的例子）就把它pass掉了，时间复杂度O(n)

代码：

class Solution {
public:
    typedef vector<int>::iterator vter;
    int maxArea(vector<int>& height) {
        auto left = height.begin();
        auto right = height.end()-1;
        int max = 0;
        while(left != right){
            vter tmp = min(left, right);
            int val = (right-left)*(*min(left, right));
            if(max < val){
                max = val;
            }
            if(tmp == left){
                ++left;
            }else{
                --right;
            }
        }
        return max;
    }
    vter min(vter a, vter b){
        return *a < *b ? a : b;
    }
};