11. Container With Most Water (M)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1,1]
Output: 1

Constraints:

• n == height.length

• 2 <= n <= 105

• 0 <= height[i] <= 104

Solution:

Greedy:

这题和接雨水问题很类似，可以完全套用前文的思路，而且还更简单。两道题的区别在于：

接雨水问题给出的类似一幅直方图，每个横坐标都有宽度，而本题给出的每个横坐标是一条竖线，没有宽度。

我们前文讨论了半天 l_max 和 r_max，实际上都是为了计算 height[i] 能够装多少水；而本题中 height[i] 没有了宽度，那自然就好办多了。

举个例子，如果在接雨水问题中，你知道了 height[left] 和 height[right] 的高度，你能算出 left 和 right 之间能够盛下多少水吗？

不能，因为你不知道 left 和 right 之间每个柱子具体能盛多少水，你得通过每个柱子的 l_max 和 r_max 来计算才行。

反过来，就本题而言，你知道了 height[left] 和 height[right] 的高度，能算出 left 和 right 之间能够盛下多少水吗？

可以，因为本题中竖线没有宽度，所以 left 和 right 之间能够盛的水就是：

min(height[left], height[right]) * (right - left)

类似接雨水问题，高度是由 height[left] 和 height[right] 较小的值决定的。

解决这道题的思路依然是双指针技巧：

用 left 和 right 两个指针从两端向中心收缩，一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案。

先直接看解法代码吧：

int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int res = 0;
    while (left < right) {
        // [left, right] 之间的矩形面积
        int cur_area = Math.min(height[left], height[right]) * (right - left);
        res = Math.max(res, cur_area);
        // 双指针技巧，移动较低的一边
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return res;
}

代码和接雨水问题大致相同，不过肯定有读者会问，下面这段 if 语句为什么要移动较低的一边：

// 双指针技巧，移动较低的一边
if (height[left] < height[right]) {
    left++;
} else {
    right--;
}

其实也好理解，因为矩形的高度是由 min(height[left], height[right]) 即较低的一边决定的：

你如果移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大；相反，如果你去移动较高的那一边，矩形的高度是无论如何都不会变大的，所以不可能使矩形的面积变得更大。

至此，这道题也解决了。