本文概览：本文以LeetCode经典题目"盛最多水的容器"为例，从暴力解法入手逐步推导双指针贪心策略，深入讲解如何通过移动短板缩小检索范围，将时间复杂度从O(n²)优化至O(n)

一、题目

题目描述

二、题目分析

给定一个非负整数数组 height，其中 height[i] 表示第 i 根垂直线的高度。每两条线与 x 轴围成一个“容器”，其容量 = 底边长度 × 短边高度
目标：找出任意两条线，使容器容积最大

思路概览

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxArea(int[] height) {
    int res = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int area = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

**思路简要说明 **

  1. 容器容量由短板决定：无论另一侧多高，水位不会超过较矮的那根线

  2. 宽度越宽，潜力越大：初始时左右指针在两端，宽度最大；若想增大容量，只能尝试“换掉短板”以期找到更高的板来补偿宽度损失

  3. 贪心策略成立：

    • 若 height[i] < height[j]，则移动 i++ —— 因为当前 i 是瓶颈，固定 j 时，任何 i > j 的组合宽度更小、高度 ≤ height[i]，容量不可能更大
    • 同理，若 height[j] ≤ height[i]，则移动 j--

三、思路详解

暴力解法入手

最自然的想法是枚举所有可能的左右边界组合 (i, j)，计算每个容器的面积并取最大值

此时的检索范围为下图全部的白色格子暴力解法的检索范围
显然可以得出以下结论

  • 时间复杂度： O(n²) , 显然销量很低 
  • 核心瓶颈：我们做了大量无效计算 , 很多组合在计算之前就可以被逻辑排除 , 需要缩小检索范围
  • 关键思考：能否在不遗漏最优解的前提下，跳过某些必然不是最优的组合？

双指针解法

思路分析

由于我们需要得出使容器容积最大 , 我们不妨选择相距最远的两个柱子看看情况 , 因为此时的宽度是最大的, 但是容器高度不一定是最大的

如下图所示，在一开始，我们考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d=8；水的高度取决于两根柱子之间较短的那个，即左边柱子的高度 h=3。水的面积就是 3×8=24
容量分析图

此时我们如果想让容量变大 , 有两条路可以选择

  • 增大宽度d, 但是这显然不可能做到, 因为此时我们选择的是相距最大的两条柱子, 宽度d已经达到上限了
  • 增大高度h, 这是可能做到的, 目前由于左边的柱子比右边的低, 所以显然容器的最大高度被限制为了h=3, 达不到h=7, 此时容器的高度由左边柱子的高度决定, 为了突破最大高度, 我们又有了两条路选择
    • 移动左柱子 , 显然此时宽度d减小, 但是容器的高度就未知了
      • 若移动后的左柱子高度大于原左柱子的高度但是小于右柱子的高度, 此时容器的容积大小变化就不确定了。此时容器的最大高度为新左柱子的高度, d减小了, 但是h增大了,所以容积可能变大也可能变小, 是不确定的
      • 若移动后的左柱子高度大于右柱子 ,此时容器的容积大小变化就不确定了。此时容器的高度就会变成右柱子的高度h=7, 上图显示的情况就是这样的, 移动后左柱子的高度h=8, 此时容积为 7×7=49, 显然大于原来的容积, 所以此时最大容积就变化为49了
      • 若移动后的左柱子高度小于原左柱子的高度, 此时容器的高度必然减小, 所以容器的容积也必然减小
    • 移动右柱子, 显然此时宽度d减小, 而右柱子的高度即使大于左柱子, 容器的高度也还是左柱子的高度 ,如果右柱子高度小于左柱子高度, 那容器的高度就会变为更小的右柱子的高度 , 在d必然减小, h可能不变或减小的情况下, 容器的体积必然是会变小的, 所以不可能选择移动右柱子

所以我们可以理解为左边的柱子和任意一个其他柱子的组合, 其容器的体积都会变小, 也就是我们可以排除掉左边的柱子了 ,只有向右移动左柱子, 容器容积的大小才可能变化

也就是说, 对于左右柱子, 我们只需要每次比较完高度之后移动较矮那一边的柱子就好了, 移动高的柱子是毫无作用的, 因为得到的结果是容积必然变小, 也就是说, 我们实现了缩小检索范围

此时按图来理解(可以看上面那张图来看左右柱子大小)

需要满足以下条件

  • i、j 都是合法的柱子下标，即 0≤i<n,0≤j<\n
  • i 在 j 的左边，即 i<\j

i 就是我们的左柱子, j 就是代表着右柱子, 我们第一次选择了(0,7), 由于左柱子矮于右柱子, 然后选择移动左柱子, 也就是i++。 此时当 i =0时, 对于 j 的任何取值都无需理会了, 全部排除, 因为对于任何 j 的取值, 容积必然变小, 需要检索的范围就变成剩下的白色格子了。在图上表示就是第0行全部涂黑, 因为第0行的最大容器容积就是(0,7)这个格子所代表的了容积了
第一次移动
排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间。我们检查右上方的单元格 (1,7)，即考虑 1 号柱子和 7 号柱子，计算容积。然后，比较两根柱子的高度, 由于右柱子矮于左柱子, 然后选择移动右柱子, 也就是j--。此时当 j =7时, 对于 i 的任何取值都无需理会了, 全部排除, 因为对于任何 i 的取值, 容积必然变小, 需要检索的范围就变成剩下的白色格子了。在图上表示就是第7列全部涂黑, 因为第7列的最大容器容积就是(1,7)这个格子所代表的了容积了
第二次移动
可以看到，无论柱子 i 和 j 哪根更长，我们都可以排除掉一行或者一列的搜索空间

此时的时间复杂度就变为了O(n)