11.盛最多水的容器

Posted on Edited on In Views: Word count in article: 1.4k Reading time ≈ 1 mins.

11 盛最多水的容器

题目链接：11. 盛最多水的容器

核心思考：最大容量的决定因素

对于这个模型和下面的示例图，我们首先要打破一个直觉陷阱：最优解中一定包含全图最高的那个柱子作为一边吗？

答案是不一定。最优解的模型不一定包含全图最高的那个柱子。

我们可以从决定水量的底层逻辑来拆解：

容量 = 两个柱子中较短的高度 * 两个柱子之间的距离

这里面存在一个经典的“木桶效应”和一个“宽度补偿”的权衡：

  1. 高度被短板限制：即使你选中了那个突破天际的最高柱子，只要和它配对的另一个柱子很矮，那最高柱子的“身高优势”就完全被浪费了，水面的实际高度只能取决于那个矮柱子。
  2. 宽度可以弥补高度：有时候，放弃中间那个极高的柱子，选择两边稍微矮一点、但距离非常远的两根柱子，反而能通过巨大的“宽度”来碾压高度带来的收益。

破局点：为什么要关注两端？

既然宽度如此重要，那就是从头和尾各找最高的柱子吗？

思路很接近了，我们确实需要关注两端的柱子。因为正如刚才说的，最开始站在数组的最左和最右两端时，我们拥有绝对的宽度优势（此时宽度是 $n-1$）。

这时候，想象一下我们已经在这两根柱子之间注水了，当前的容量是由这两端的柱子里较矮的那一根决定的（木桶短板效应）。

由于我们要向内去寻找其他的柱子，所以每往中间走一步，宽度必定会减小。在宽度持续折损的情况下，要想让总容量不仅不亏反而更大，唯一的出路就是——想办法让水位线升高，以此来弥补宽度的损失。

核心逻辑：该移动哪根柱子？

我们极端一点想：假设现在左边的柱子很矮，右边的柱子很高，应该移动哪一边？

  • 假设我们移动那根“高”柱子：
    我们放弃了高柱子，向内寻找。哪怕我们运气爆棚，遇到了一根直插云霄的新柱子，水位线的上限依然会被留在原地的“矮柱子”死死卡住。结果就是：宽度变小了，高度不仅没增加，甚至可能更矮。这波操作绝对亏本，容量必定缩水。

  • 假设我们移动那根“矮”柱子：
    我们放弃矮柱子，向内寻找。虽然宽度依然变小了，但我们有可能会遇到一根更高的柱子！只要新找到的柱子比原来那根被放弃的矮柱子高，水位线就有可能被右边那根原本的高柱子拉上来。这时候，高度带来的收益就有可能碾压宽度的损失，从而刷新最大容量。

双指针解法

基于以上推论，我们很容易得到正解思路：头尾各一个指针，每次只移动更短的那个指针。

因为在宽度必定减少的前提下，保留长板、抛弃短板，是我们唯一可能让水位线上升、从而突破当前容量极限的机会。

算法步骤

  1. 初始化：左右指针分别指向数组的最头和最尾。
  2. 计算并记录：计算当前两个指针构成的容器容量，如果比“历史最大容量”大，就更新记录。
  3. 移动短板：对比左右指针指向的柱子高度，毫不犹豫地把较矮的那个指针向内移动一格。如果一样高，移哪个都行。
  4. 循环：重复步骤 2 和 3，直到左右指针相遇，游戏结束。

精妙之处：安全剪枝
我们每次移动短板，实际上是在安全地剪枝——我们用严密的逻辑证明了，包含当前短板的所有其他向内的组合，容量必定小于当前值，所以可以直接批量抛弃，一行代码都不用多跑。这就把一个原本需要暴力枚举、时间复杂度为 $O(n^2)$ 的问题，极其优雅地降维到了 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        # 长度为n的数组 index头0尾n-1
        left = 0
        right = n-1
        cur_ans = (right - left)  * min(height[left],height[right])
        # 宽度 = right - left + 1
        while(left != right):
            if (height[left]<=height[right]):
                left += 1;
            else:
                right -= 1;
            temp_ans = (right - left)  * min(height[left],height[right])
            cur_ans = max(temp_ans,cur_ans)
        return cur_ans

image-compressed.png

进阶优化

但我想到我没必要每次移动一格就算一次，如果没有找到更高的那就没有价值。

我们在向内移动的过程中，可以连续跳过那些不大于当前短板高度的废柱子，以此进一步提升效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0
        while left < right:
            # 锁定当前左右边界的高度
            h_left = height[left]
            h_right = height[right]
            # 计算当前这步的容量并更新最大值
            current_area = min(h_left, h_right) * (right - left)
            if current_area > max_area:
                max_area = current_area
            # 移动短板，并无视沿途的废柱子
            if h_left < h_right:
                # 向内跳过所有不大于当前短板高度的废柱子
                while left < right and height[left] <= h_left:
                    left += 1
            else:
                while left < right and height[right] <= h_right:
                    right -= 1
        return max_area

image-compressed.png