LeetCode 补拙笔记

0. 前言

• 日期：2026.06.09
• 题目：42. 接雨水
• 难度：困难
• 标签：数组、双指针、动态规划

1. 题目理解

问题描述： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：蓝色部分表示雨水，总共可接 6 个单位的雨水。

2. 解题思路

核心观察

• 单个位置能接的雨水量，由该位置左右两侧的最大高度中较小值减去自身高度决定： water[i] = min(leftMax[i], rightMax[i]) - height[i]。
• 优化版使用双指针，用 leftMax 和 rightMax 动态维护两侧最大值，一次遍历即可计算总水量，无需额外数组。

算法步骤

1. 初始化双指针 left、right 分别指向首尾，leftMax、rightMax 记录两侧当前最大值；
2. 若 height[left] < height[right]，则以 leftMax 为基准，更新水量或 leftMax，左指针右移；
3. 否则以 rightMax 为基准，更新水量或 rightMax，右指针左移；
4. 遍历结束，返回总水量。

3. 代码实现

package lc0_lc99.lc42;

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        left[0] = height[0];
        right[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            left[i] = Integer.max(left[i - 1], height[i]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Integer.max(right[i + 1], height[i]);
        }
        for (int i = 0; i < height.length; i++) {
            res += Math.min(left[i], right[i]) - height[i];
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public int trap(int[] height) {
    // 边界：数组为空或长度不足2，接不到雨水
    if (height == null || height.length < 2) {
        return 0;
    }
    int left = 0;
    int right = height.length-1;
    int leftMax = 0;
    int rightMax = 0;
    int ans = 0;
    while(left < right){
        if(height[left] < height[right]){
            if(height[left]>= leftMax){
                leftMax = height[left];
            }else{
                ans = ans + leftMax-height[left];
            }
            left++;
        }else{
            if(height[right] >= rightMax){
                rightMax = height[right];
            }else{
                ans = ans + rightMax -height[right];
            }
            right--;
        }
    }
    return ans;
}
}

5. 复杂度分析

• 动态规划版
  • 时间复杂度：$O(n)$，三次线性遍历。
  • 空间复杂度：$O(n)$，左右最大高度数组。
• 双指针优化版
  • 时间复杂度：$O(n)$，一次遍历。
  • 空间复杂度：$O(1)$，仅常数变量。

6. 总结

• 核心：左右两侧最大高度的较小值决定单个位置的接水量。
• 优化亮点：用双指针动态维护两侧最大值，省去额外数组，空间复杂度从 $O(n)$ 降至 $O(1)$。
• 关键：哪边高度小，哪边的指针移动，保证了 leftMax 或 rightMax 是当前的有效瓶颈。