题目

给你一个长度为n的整数数组height，其中height[i]表示坐标(i, height[i])处的一条垂直线（柱子）。你需要选择两条垂直线，与x轴共同构成一个容器，求出这个容器能盛的最多水量（面积）。

注意：

• 容器不能倾斜。
• 水量 = min(height[i], height[j]) * (j - i)，其中i < j。
• 返回最大水量。

示例：

• 输入：height = [1,8,6,2,5,4,8,3,7]
• 输出：49
• 解释：选择索引1（高度8）和索引8（高度7），min(8,7)=7，宽度=7，面积=49。

约束：

• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

题目链接🔗

思路

这个问题可以使用双指针法高效求解，时间复杂度为O(n)。核心思想是从数组两端开始，使用两个指针向中间移动，总是移动高度较小的指针（短板），因为它限制了当前面积。通过贪心策略，逐步逼近最大面积。

• 初始化左指针l = 0，右指针r = n-1，最大面积ans = 0。
• while (l < r)：
  • 计算当前面积：area = min(height[l], height[r]) * (r - l)。
  • 更新ans = max(ans, area)。
  • 如果height[l] <= height[r]，则l++；否则r--。
• 返回ans。

这种方法从最大宽度开始，移动短板以追求更高的高度，从而有机会增大面积。下面我们通过数学证明来验证其正确性。

数学证明

双指针法的正确性基于贪心和反证法。我们证明：(1) 局部移动正确；(2) 全局不会错过最优解。

证明1: 局部正确性（为什么移动短板？）

假设当前l和r，且height[l] <= height[r]（对称情况类似）。

• 当前面积A = height[l] * (r - l)。

• 如果移动长板（r--到r'）：

  • 新高度min' = min(height[l], height[r']) <= height[l]。
  • 新宽度(r' - l) = (r - l) - 1 < 原宽度。
  • 新面积A' <= height[l] * ((r - l) - 1) < A（严格小于）。
  • 结论：无益，不会产生更大面积。

• 如果移动短板（l++到l'）：

  • 新高度min' = min(height[l'], height[r])，可能> height[l]。
  • 新面积可能> A。

通过归纳：初始步正确，每步移动短板保持性质，整个算法局部正确。

证明2: 全局完整性（不会错过最优解）

假设存在最优对(i, j)，面积A_max = min(height[i], height[j]) * (j - i) 是全局最大。我们证明算法必在某步计算它。

• 反证假设：算法从未计算(i, j)。

• 算法性质：l从0单增，r从n-1单减；初始l <= i < j <= r。

• 关键：算法只“跳过”不可能是最优的柱子对。

  • 令(i, j)为最优，假设height[i] <= height[j]。
  • 当l第一次到达i时，r必然还在 >= j（因为r只在height[r]是短板时减小，且height[j] >= height[i]`）。
  • 然后，继续移动，直到r = j，此时计算(i, j)。

• 归纳证明：

  • 基例：n=2，初始计算。
  • 假设对<n成立。对n，第一步计算(0, n-1)。如果它是最大，完成；否则移动短板，子数组由假设覆盖。

结论：所有可能的最优对都会被访问，算法正确。

代码

C++

int maxArea(int* height, int heightSize) {
    int l = 0, r = heightSize - 1;
    int ans = 0;
    int min = 0, area = 0;
    while (l < r) {
        if (height[l] < height[r]) min = height[l];
        else min = height[r];
        area = min * (r - l);
        if (ans < area) ans = area;
        if (height[l] <= height[r]) {
            ++l;
        } else {
            --r;
        }
    }
    return ans;
}

Java

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

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        
        while l < r:
            min_height = min(height[l], height[r])
            area = min_height * (r - l)
            ans = max(ans, area)
            if height[l] <= height[r]:
                l += 1
            else:
                r -= 1
        
        return ans

复杂度分析

时间复杂度

O(n)，其中n是height数组的长度。每个指针最多移动n次，整个数组被遍历一次。

空间复杂度

O(1)，只使用了常量额外空间，不依赖输入大小。

总结

双指针法巧妙地解决了这个问题，通过贪心移动短板，避免了暴力枚举的低效。数学证明确保了算法的正确性，加深了对贪心算法的理解。