11. 盛最多水的容器

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。

样例

---

Example

示例 1：

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

示例 2：
**输入：**height = [1,1]
**输出：**1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

思路

---

设左指针为l，右指针为r，那么当前区间的盛水量就为(r - l) * Math.min(height[l], height[r])。
那么当然是要想宽度和高度都尽量地大，但是一开始我们并不知道哪个最高，因此我们可以先从最宽开始，取l = 0, r = height.length - 1，然后指针逐渐向里移动，寻求更高的高度。那么接下来要决定移动哪一边的指针，通过分析可以得出我们需要移动高度较小的一方，因为如果移动了较高的一方，宽度变小了，而高度Math.min(height[l], height[r]显然不可能增加，因此结果会更小。直到两指针相遇，保留最大结果即可。

答案

---

Java

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l != r) {
            ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
            if (height[l] <= height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}