BM93　盛水最多的容器¶

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

牛客原题　源码

讲解章节：双指针与滑动窗口

一句话

左右双指针夹逼，每轮舍弃较矮的那条边。

解题思路¶

这题考什么¶

一个「每步能安全排除一个候选」的对撞双指针论证。选两根柱子 i < j 当容器两壁，装水量 = 宽 * 高 = (j - i) * min(h[i], h[j])，水面被矮的那一边限制住，这是整题的支点。

枚举所有 (i, j) 是 O(n^2)。改成左右双指针 l = 0、r = n-1，每轮先结算当前面积，再把矮的那一侧往里挪一格：

while l < r:
    ans = max(ans, (r - l) * min(h[l], h[r]))
    if h[l] < h[r]: l += 1
    else:           r -= 1

为什么可以放心丢掉矮边？设 h[l] < h[r]。在所有以 l 为左壁的搭配里，此刻的 r 已经是最宽的一个；再换任何 j < r 当右壁，宽度必然变小，而高度 min(h[l], h[j]) <= h[l] 也不可能超过现在这个值，面积一定不增。既然含 l 的组合的上限已经被算过，l 就可以永久出局。对称地，h[l] >= h[r] 时 r 出局。每步排除一根柱子，n 步内扫完，不漏最优解。

走一遍 [1,7,3,2,4,5,8,2,7]：

l=0(高1) r=8(高7)  面积 8*1=8   -> 丢左
l=1(高7) r=8(高7)  面积 7*7=49  -> 相等，丢右
l=1(高7) r=7(高2)  面积 6*2=12  -> 丢右
l=1(高7) r=6(高8)  面积 5*7=35  -> 丢左
...后面的宽度都不足以翻盘，答案 49

数据规模与复杂度¶

n <= 1e5，height[i] <= 1e4，时限「其他语言 2 秒」，题面保证答案不超过 32 位有符号整数上限。双指针时间 O(n)、空间 O(1)。暴力枚举是 O(n^2) = 1e10 次面积计算， Python 下慢出好几个数量级。

坑在哪¶

移动的必须是矮的那一侧。挪高的一侧会同时丢掉宽度与高度上限，真正的最优解可能就此被跨过——正确性完全依赖上面那段排除论证。
宽度是 r - l 而不是 r - l + 1。装水的是两壁之间的空隙，柱子本身不占宽度，样例 [2,2] 的答案 2 就是 1 * 2 而不是 2 * 2。
两侧等高时丢哪边都行：此时两边的排除论证同时成立。但两个分支必须都动指针，写成只在严格不等时移动会死循环。
n < 2 视为不能形成容器，返回 0。while l < r 对 n = 0 或 1 一次都不执行， ans 保持 0，不必额外特判。n = 0 时 right 会是 -1，但循环条件先行短路，不会有越界访问。

参考实现¶

solutions/nowcoder/BM93/sol.py
from typing import List, Optional


class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 从最宽的一对柱子起步，之后每步只会变窄，靠高度的增长去翻盘
        left, right = 0, len(height) - 1
        ans = 0
        while left < right:                       # n < 2 时一次都不进入，直接返回 0
            # 宽度取 r - l：装水的是两壁之间的空隙，柱子本身不占宽度
            area = (right - left) * min(height[left], height[right])
            if area > ans:
                ans = area
            # 矮的一侧是短板：以它为壁的组合，最宽的那个已经算过，再窄只会更小，
            # 因此可以永久淘汰。等高时淘汰哪边都成立，两个分支都必须移动指针
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans

BM93 盛水最多的容器¶