双指针与滑动窗口困难3 种解法

#42接雨水

给定柱状图高度，计算下雨后柱子之间能够承接的水量。

#数组#双指针#动态规划

解题主线

位置 i 的水量为 min(左侧最高柱, 右侧最高柱) - height[i]。

前后缀最大值数组把每个位置重复扫描边界的成本从 O(n) 降为 O(1)。

双指针中较低一侧的边界已足以确定该侧当前位置的水量，因此可以立即结算并向内移动。

解法 1：逐位置扫描边界

对每个内部位置分别向左、向右寻找最高柱，再由较低边界计算该位置积水，作为直观基线。

时间复杂度

O(n²)

空间复杂度

O(1)

42. 接雨水 · 逐位置扫描边界

java

final class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;

        int water = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int leftMaximum = 0;
            int rightMaximum = 0;
            for (int left = i; left >= 0; left--) {
                leftMaximum = Math.max(leftMaximum, height[left]);
            }
            for (int right = i; right < height.length; right++) {
                rightMaximum = Math.max(rightMaximum, height[right]);
            }
            water += Math.min(leftMaximum, rightMaximum) - height[i];
        }
        return water;
    }
}

对每个内部位置分别向左、向右寻找最高柱，再由较低边界计算该位置积水，作为直观基线。

保留为公式的直接实现；相比旧代码，拆分左右扫描并移除了 System.out.println。

解法 2：前后缀最大值动态规划

预处理每个位置左侧与右侧（均含自身）的最高柱，再线性汇总所有位置的积水。

时间复杂度

O(n)

空间复杂度

O(n)

42. 接雨水 · 前后缀最大值动态规划

java

final class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;

        int n = height.length;
        int[] leftMaximum = new int[n];
        int[] rightMaximum = new int[n];
        leftMaximum[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMaximum[i] = Math.max(leftMaximum[i - 1], height[i]);
        }
        rightMaximum[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMaximum[i] = Math.max(rightMaximum[i + 1], height[i]);
        }

        int water = 0;
        for (int i = 1; i < n - 1; i++) {
            water += Math.min(leftMaximum[i], rightMaximum[i]) - height[i];
        }
        return water;
    }
}

预处理每个位置左侧与右侧（均含自身）的最高柱，再线性汇总所有位置的积水。

解法 3：双指针压缩空间

从两端向内维护 leftMaximum 与 rightMaximum；每轮结算当前最高边界较低的一侧。

时间复杂度

O(n)

空间复杂度

O(1)

42. 接雨水 · 双指针压缩空间

java

final class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;

        int left = 0;
        int right = height.length - 1;
        int leftMaximum = 0;
        int rightMaximum = 0;
        int water = 0;

        while (left <= right) {
            leftMaximum = Math.max(leftMaximum, height[left]);
            rightMaximum = Math.max(rightMaximum, height[right]);
            if (leftMaximum <= rightMaximum) {
                water += leftMaximum - height[left];
                left++;
            } else {
                water += rightMaximum - height[right];
                right--;
            }
        }
        return water;
    }
}

从两端向内维护 leftMaximum 与 rightMaximum；每轮结算当前最高边界较低的一侧。

边界与易错点

旧 trapDP 在空数组上会访问 lMax[0] 和 rMax[-1]；所有整理后的解法都先处理空输入。
旧 trapBase 在核心循环打印调试信息，既污染提交输出也扭曲运行成本；整理后已移除。
旧注释把 O(n) 的前后缀 DP 标成“会超时”；其准确复杂度是 O(n) 时间、O(n) 空间，真正的基线才是 O(n²)。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/zhard/Q042_trapWater.java