LC11　盛最多水的容器¶

中等通过率 61.9%python3核心代码模式双指针样例通过牛客 AC贪心数组双指针

一句话

两端相向的双指针，每次丢掉较矮的那条边。

解题思路¶

这题考什么¶

两条线 i < j 围出的水量是 (j - i) * min(height[i], height[j])—— 宽度取下标差，高度受较矮的一边限制（不能倾斜容器）。枚举所有数对是 O(n^2)，n = 1e5 时 5e9 次，不可行。

双指针从两端往里收，靠的是一个能安全丢弃候选的论证：设当前左右指针为 l、r，且 height[l] <= height[r]。那么「以 l 为左边界」的所有方案里，当前这个 (l, r) 已经是最好的—— 任何 l < r' < r 的组合，宽度只会更小（r' - l < r - l），高度也不会超过 height[l]（min 里已经卡着 height[l] 了）。既然含 l 的最优解已经算过，l 这条边就可以永久退出，指针右移。对称地，height[r] < height[l] 时把 r 左移。

每一步都排除掉一条边，n 条边最多排除 n 次，双指针只走一趟。这是「相向双指针」的典型形态，见双指针与滑动窗口。

移动较矮的那一侧是关键，反过来必错：若移动较高的一侧，宽度减小、而高度仍被那条矮边压着，新面积一定不大于旧面积，等于白走一步，而真正可能更优的组合（换掉矮边）反倒永远试不到。

数据规模与复杂度¶

2 <= n <= 1e5，0 <= height[i] <= 1e4。最大面积不超过 1e5 * 1e4 = 1e9，Python 整数不会溢出。时间 O(n)：l 与 r 加起来只走 n 步；空间 O(1)，只有几个标量。暴力枚举是 n 的平方除以二 = 5e9 次乘法，差着好几个数量级。

坑在哪¶

高度取 min 不是 max。水面由短板决定，取 max 会把每个样例都算大。
必须移动较矮的一侧。移动较高的一侧时面积单调不增（宽变小、短板没换掉），指针白走，最优解会被跳过。
相等时移哪边都行。height[l] == height[r] 时，含 l 的最优与含 r 的最优都已经在当前这步取到，两条边同时可以丢弃，本题解按条件写法移动 l。
循环条件是 while l < r 而不是 <=。l == r 时宽度为 0，算出来的面积恒为 0，多算一轮没有意义。
高度可以是 0（题面下界就是 0）。这不需要特判：短板为 0 时面积算出来是 0，不会污染最大值，而且下一步正好把这条零高度的边丢掉。
严格比对：答案是一个整数，没有多解。

样例复核¶

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，n = 9。

l=0 r=8  min(1,7)=1  面积 8*1=8    左矮 -> l=1
l=1 r=8  min(8,7)=7  面积 7*7=49   右矮 -> r=7   <- 答案
l=1 r=7  min(8,3)=3  面积 6*3=18   右矮 -> r=6
l=1 r=6  min(8,8)=8  面积 5*8=40   相等 -> l=2
l=2 r=6  min(6,8)=6  面积 4*6=24   左矮 -> l=3
l=3 r=6  min(2,8)=2  面积 3*2=6    左矮 -> l=4
l=4 r=6  min(5,8)=5  面积 2*5=10   左矮 -> l=5
l=5 r=6  min(4,8)=4  面积 1*4=4    左矮 -> l=6
l=6 r=6  退出

最大 49，与样例一致。注意第二步：若此时错误地移动较高的一侧（l 右移）， r=8 这条边会被留着，但含它的最优解已经算完，后面全是更小的面积。

参考实现¶

solutions/leetcode/LC11/sol.py
from typing import List, Optional


class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 相向双指针：从最宽的一对边起步，之后宽度只会变小，
        # 所以想变优只能靠换掉短板
        left = 0
        right = len(height) - 1
        ans = 0
        # l == r 时宽度为 0，面积恒为 0，没必要再算，所以是严格小于
        while left < right:
            # 水面由较矮的一边决定（容器不能倾斜），宽度是下标差
            h = height[left] if height[left] <= height[right] else height[right]
            area = (right - left) * h
            if area > ans:
                ans = area
            # 丢弃较矮的那条边：以它为边界的最优组合就是当前这个（再往里宽度更小、
            # 高度仍被它压着），所以可以永久排除。移动较高的一侧则面积单调不增
            if height[left] <= height[right]:
                left += 1               # 相等时两条边都可丢，移哪边都不影响答案
            else:
                right -= 1
        return ans

LC11 盛最多水的容器¶