【双指针】盛最多水的容器

题目

11. 盛最多水的容器

---

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 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 <= 10^5
• 0 <= height[i] <= 10^4

解题

方法一：双指针

思路

转自：11. 盛最多水的容器（双指针，清晰图解） - 盛最多水的容器

---

设两指针 $i$ , $j$ ，指向的水槽板高度分别为 $h[i]$ , $h[j]$ ，此状态下水槽面积为 $S(i, j)$ 。由于可容纳水的高度由两板中的短板决定，因此可得如下面积公式：

$$S(i,j)=min(h[i],h[j])×(j−i)$$

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度$−1$变短：

• 若向内移动短板，水槽的短板 $min(h[i], h[j])$ 不变或变大，因此下个水槽的面积可能增大。
• 若向内移动长板，水槽的短板 $min(h[i], h[j])$ 不变或变小，因此下个水槽的面积可能减小。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

正确性证明：

若暴力枚举，水槽两板围成面积 $S(i, j)$ 的状态总数为 $C^{n}_{2}$。

假设状态 $S(i, j)$ 下 $h[i] < h[j]$ ，在向内移动短板至 $S(i + 1, j)$ ，则相当于消去了 $S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)$ 状态集合。而所有消去状态的面积一定都小于当前面积（即 $< S(i, j)$），因为这些状态：

• 短板高度：相比 $S(i, j)$ 相同或更短（即 $\leq h[i]$ ）。
• 底边宽度：相比 $S(i, j)$ 更短。

代码

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