首页笔记编程算法

    ✨ 我是 Muzi 的「文章捕手」，擅长在文字的星海中打捞精华。每当新的篇章诞生，我就会像整理贝壳一样，将思想的闪光点串成珍珠项链~

    本文以LeetCode第11题“盛最多水的容器”为例，详细介绍了两种解题思路：暴力枚举法和双指针贪心法。暴力枚举法通过双重循环计算所有可能面积，时间复杂度为O(n²)，效率低下且面试不推荐。双指针贪心法则利用左右指针从数组两端向内移动，始终移动较短边指针以寻找更大面积，时间复杂度优化至O(n)，空间复杂度为O(1)。文章通过代码示例和动画演示阐释了双指针法的核心思想及正确性，强调了“移动短边突破瓶颈”的贪心策略，并总结了双指针法的通用模板及其在相关经典题目中的应用，具有较高的实用价值和面试指导意义。

    # 一、题目描述（LeetCode 11.盛最多水的容器）

    给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

    找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

    说明：你不能倾斜容器。

    约束条件：

    • n == height.length

    • 2 <= n <= 10^5

    • 0 <= height[i] <= 10^4

    示例：

    • 输入：height = [1,8,6,2,5,4,8,3,7]，输出：49（第 2 条线和第 9 条线之间）

    • 输入：height = [1,1]，输出：1

    面积公式：area = (right - left) × min(height[left], height[right])

    # 二、两种解题思路 & Java代码

    # 1. 暴力枚举法（新手理解，不推荐面试）

    # 思路

    双重循环枚举所有可能的两条线组合，计算每一对构成的容器面积，取最大值。外层遍历左指针，内层遍历右指针（你最初描述的思路就是这种）。

    # 复杂度

    时间复杂度：O(n²)，空间复杂度：O(1)

    # 代码

    class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for (int left = 0; left < height.length; left++) {
            for (int right = left + 1; right < height.length; right++) {
                int area = (right - left) * Math.min(height[left], height[right]);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}

    # 问题

    • 当 n = 10^5 时，需要执行约 5 × 10^9 次运算，必定超时

    • 面试中面试官一定会追问：能否优化到 O(n)？

    # 2. 双指针贪心法（面试最优解）⭐

    # 核心思路

    使用两个指针 left 和 right，分别从数组最左端和最右端开始：

    1. 计算当前两条线围成的面积，更新最大值

    2. 比较两条线的高度，移动较短的那条线的指针向内收缩

    3. 重复直到两指针相遇

    # 为什么移动短的指针？

    这是本题最关键的理解：

    • 面积 = 宽度 × 较矮的高度

    • 不管移动哪边，宽度一定在缩小

    • 如果移动高的指针，新面积的高度不会超过原来的矮指针（受限于 min），面积只可能更小

    • 如果移动矮的指针，虽然宽度缩小，但有可能遇到更高的线，面积有机会变大

    结论：只有移动矮的那一边，才存在"面积变大"的可能性。

    # 复杂度

    时间复杂度：O(n)，空间复杂度：O(1)

    # 代码

    class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, area);
            // 移动较短的那条线
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

    # 三、算法执行过程动图演示

    以输入 height = [1,8,6,2,5,4,8,3,7] 为例，逐步演示双指针贪心法：

    # 初始状态

    索引:  0  1  2  3  4  5  6  7  8
高度:  1  8  6  2  5  4  8  3  7
       ↑                       ↑
     left=0                  right=8

    # 第 1 步：left=0, right=8

    高度:  1  8  6  2  5  4  8  3  7
       ↑                       ↑
     left=0                  right=8

area = (8 - 0) × min(1, 7) = 8 × 1 = 8
maxArea = 8

左边矮 (1 < 7) → 左指针右移

    # 第 2 步：left=1, right=8

    高度:  1  8  6  2  5  4  8  3  7
          ↑                    ↑
       left=1               right=8

area = (8 - 1) × min(8, 7) = 7 × 7 = 49  🔥 新最大值！
maxArea = 49

右边矮 (7 < 8) → 右指针左移

    # 第 3 步：left=1, right=7

    高度:  1  8  6  2  5  4  8  3  7
          ↑                 ↑
       left=1            right=7

area = (7 - 1) × min(8, 3) = 6 × 3 = 18
maxArea = 49（未超过）

右边矮 (3 < 8) → 右指针左移

    # 第 4 步：left=1, right=6

    高度:  1  8  6  2  5  4  8  3  7
          ↑              ↑
       left=1         right=6

area = (6 - 1) × min(8, 8) = 5 × 8 = 40
maxArea = 49（未超过）

两边等高 (8 == 8) → 移动任意一边，这里移动右指针

    # 第 5 步：left=1, right=5

    高度:  1  8  6  2  5  4  8  3  7
          ↑           ↑
       left=1      right=5

area = (5 - 1) × min(8, 4) = 4 × 4 = 16
maxArea = 49（未超过）

右边矮 (4 < 8) → 右指针左移

    # 第 6 步：left=1, right=4

    高度:  1  8  6  2  5  4  8  3  7
          ↑        ↑
       left=1   right=4

area = (4 - 1) × min(8, 5) = 3 × 5 = 15
maxArea = 49（未超过）

右边矮 (5 < 8) → 右指针左移

    # 第 7 步：left=1, right=3

    高度:  1  8  6  2  5  4  8  3  7
          ↑     ↑
       left=1 right=3

area = (3 - 1) × min(8, 2) = 2 × 2 = 4
maxArea = 49（未超过）

右边矮 (2 < 8) → 右指针左移

    # 第 8 步：left=1, right=2

    高度:  1  8  6  2  5  4  8  3  7
          ↑  ↑
       left=1 right=2

area = (2 - 1) × min(8, 6) = 1 × 6 = 6
maxArea = 49（未超过）

右边矮 (6 < 8) → 右指针左移

    # 结束：left=1, right=1

    两指针相遇，循环结束

最终结果：maxArea = 49

    总结：只用了 8 步就找到最优解，而暴力枚举需要 36 步（C(9,2)）。数组越大，优势越明显。

    # 四、为什么这个贪心策略是正确的？

    很多人会担心："跳过的那些组合里，万一有更大的面积怎么办？"

    用反证法说明。假设最优解是 left=i, right=j，我们证明算法一定不会跳过它：

    1. 当指针走到包含 (i, j) 的状态时，如果 height[i] < height[j]，算法会移动 left（矮的），而不是 right

    2. 这意味着 right 会一直等到 left 到达 i 之后才开始移动

    3. 所以 (i, j) 这个组合一定会被计算到，不会被跳过

    一句话总结：短的那边是"瓶颈"，瓶颈不突破，面积不可能更大。所以只有突破瓶颈（移动短的）才有意义。

    # 五、关键问题解答

    # 1. 两边等高时移动哪边？

    两边等高时，移动任意一边都可以。因为：

    • 不管移动哪边，新的面积高度都不会超过当前的等高值

    • 两边都可能是瓶颈的一部分，移动哪边都不会错过最优解

    • 代码中走 else 分支（移动右边），完全没问题

    # 2. 为什么不需要考虑中间被跳过的组合？

    当移动 left（因为左边矮）时，所有 (left, right-1), (left, right-2), ... 这些组合的面积都不会超过当前值。因为它们的宽度更小，而高度仍然被 height[left] 限死。所以这些组合可以直接跳过。

    # 3. 和你的暴力思路有什么关系？

    你最初的思路是"固定左指针，遍历右指针，取最大值，再移动左指针重复"。逻辑正确，但是 O(n²)。双指针贪心法的精妙之处在于：利用"移动短边"这个规则，提前排除了大量不可能更优的组合，把枚举量从 O(n²) 压缩到 O(n)。

    # 六、双指针法核心模板（必背）

    # 核心结论

    当题目涉及"数组两端向内收缩、求最大/最小面积或区间"时 → 第一时间想到左右双指针 + 贪心移动

    # 通用模板

    int left = 0, right = nums.length - 1;
int result = 初始值;
while (left < right) {
    // 计算当前区间的值
    result = update(result, 当前值);
    // 贪心策略：移动"瓶颈"那一端
    if (nums[left] < nums[right]) {
        left++;
    } else {
        right--;
    }
}
return result;

    # 三大经典左右双指针题

    题目 贪心移动规则 求什么
    盛最多水的容器（本题） 移动较短的线 最大面积
    接雨水（LeetCode 42） 移动较短的边 总蓄水量
    两数之和 II（LeetCode 167） 和大了移右，和小了移左 目标下标

    # 秒杀口诀

    两头夹，算面积；谁短移谁，直到相遇。

    # 七、复杂度分析

    解法 时间复杂度 空间复杂度
    暴力枚举法 O(n²) O(1)
    双指针贪心法 O(n) O(1)

    • 时间复杂度：left 和 right 总共移动 n-1 次，每次操作 O(1) → O(n)

    • 空间复杂度：只用了三个变量（left, right, maxArea） → O(1)