题目

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 and n is at least 2.

分析

粗略看只能想到枚举，复杂度为O(n^2)，但是好像太简单了。提交试了下，果然超时=_=
一开始往dp方向想了半天没有进展，后来发现这题在题解中是放在贪心这一章的。
策略是从最远的两条木板height[start]和height[end]开始，计算其容积。再将这两条木板中较小的一条往中间移动，这样可以达到O(n)的复杂度。
合理性分析：比如，当height[start]<height[end]时，令start++其实是舍弃了原start处木板和其右边木板的组合，但是这些组合的距离小于原start和end，且高度小于等于原木桶的高度，所以必然比原木桶的容积小，可以舍去。

实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int start,end,ans;
        start=0; end=height.size()-1; ans=0;
        while(start<end){
            ans = max(ans, min(height[start], height[end])*(end-start));
            if(height[start]<=height[end])
                start++;
            else
                end--;
        }
        return ans;
    }
};

思考

贪心算法就像脑筋急转弯...我也不知道说啥...