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

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

---

题意是x轴上立着一堆线段，从这些线段中找两根和x轴构成一个木桶，问哪个木桶能装最多的水。 暴力枚举的话，是$O(n^2)$的。我们可以用贪心的思路来解决：要使木桶装更多的水，短板越长越好，且两根线之间的距离越长也越好。 设置首尾指针i,j，计算由i,j夹到的木桶的体积（这里简单点，面积即可），如果height[i]<height[j]，则i++，因为短板越长越好，所以这相当于抛弃了height[i]，保留height[j]，底板减1。
完整代码如下：

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int mA = 0, i = 0, j = height.size() – 1;
        while (i != j) {
            int cur = min(height[i], height[j]) * (j – i);
            if (cur > mA)
                mA = cur;
            if (height[i] < height[j])
                i++;
            else
                j--;
        }
        return mA;
    }
};

本代码提交AC，用时24MS。
二刷。
证明贪心方法的正确性一般用反证法，推出矛盾即可，证明过程见讨论区：https://discuss.leetcode.com/topic/503/anyone-who-has-a-o-n-algorithm。

三刷。反证法过程：刚开始的时候l=0,r=n-1，假设此时height[l]<height[r]，则此时的组合对l来说是它能形成最大面积的情况。因为x轴长度最大，当r往左边走的时候，x肯定会变小；如果r往左走遇到比l更短的y，则总的y变短，面积变小；如果r往左走遇到比l更长的y，则依然是l作为y，但因为x已经变小了，所以面积依然变小。总之，每一次组合，都是对更短的那个柱子的最大面积，而更长的柱子还有可能和其他柱子组成更大的面积，所以我们每次丢掉短柱子，保留长柱子。