<数据结构/算法> leetcode hot100系列. 110.盛水最多的容器

[LeetCode hot 100] 110. 盛水最多的容器

题目链接

最烦这种题，因为每次都感觉自己那么接近答案，就是做不出来，像个傻子一样。

怎样思考这个问题？首先我们从左往右看一看，假如有两根柱子，左边的柱子比右边的高，那么当选取这两个柱子之一作为左边的容器壁时，右边的柱子是一定会输的。

考虑数组的左右两个端点，假如左边的柱子更矮，那么右边的柱子无论再怎么高也没有用，这就是所谓的木桶效应。所以事实上以最左侧柱子为左端点的容器都不需要看了，因为不会有比现在更大的了。这也就是说，最左侧的柱子被“pass”了。

那么接下来就算一下这个容器的容量，然后把最左侧的柱子扔了，换第二个，也就是left指针右移。对于新的左右端点，运用同样的思路，排掉较短的那一根，如此循环直到左右端点相遇。

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