11. Container With Most Water.md

11. 盛最多水的容器

给定 n 个非负整数 a₁，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

 

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解法一（穷举，超时错误）：

//时间复杂度O(n^2), 空间复杂度O(1)
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size(), maxArea = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                maxArea = max(maxArea, (j - i) * min(height[i], height[j]));
            }
        }
        return maxArea;
    }
};

解法二（双指针）：

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int maxArea = 0;
        while(i < j) {
            maxArea = max(maxArea, (j - i) * min(height[i], height[j]));
            if(height[i] > height[j]) j--;
            else i++;
        }
        return maxArea;
    }
};

解法一：

穷举，很容易想到，二次的时间复杂度。

解法二：

双指针。指针i指向数组首元素，j指向数组尾元素，两指针相向移动，直到i >= j时停止。

指针移动的规则是，每次只移动所指向元素较小者的指针。（如果两元素大小相等，移动任意一个即可）

指针移动过程中，使用变量maxArea记录下所有面积的最大值，最后返回maxArea。

解法二的算法并没有遍历所有情况，而是尽量选择访问面积较大的情况。最开始两指针位于数组的首尾，每次都选择移动元素小者的指针。

官方题解里有解释，如果每一步的策略是移动值较大者的指针，由于短板并没有变，那移动后的面积必定小于移动之前的面积；相反如果采用相反的策略，那移动后的面积有可能会比当前面积有所增加。这个解释说明了为什么要移动较小者的指针，但并没有说明为什么该算法不会错过最优解。

我更倾向于一位网友的解释。假设输入为[1,8,6,2,5,4,8,3,7]，我们要找的是一个i、j所夹的范围，使其组成的面积最大。

1. 最初i、j从最两端开始，i指向1，j指向7。由于1比7小，此时已经证明以i（指向1）为左边界的所有情况的最大面积为1 * 8 = 8。
2. 所以i指点针向右移指向了8，8大于7，此时又证明了以j（指向8）为右边界的所有情况的最大面积为7 * 7 = 49。
3. 然后继续移动指针，每移动一次，就证明了一种边界的最大值。对于最优解，也一定是遍历过程中被证明的其中之一。

2019/09/16 21:57