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

#42接雨水

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

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

原题

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

查看原题

解题主线

位置 i 的水量为 min(左侧最高柱, 右侧最高柱) - height[i]。
前后缀最大值数组把每个位置重复扫描边界的成本从 O(n) 降为 O(1)。
双指针中较低一侧的边界已足以确定该侧当前位置的水量，因此可以立即结算并向内移动。

解法 1：逐位置扫描边界

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

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

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)

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[i] 保存区间 [0, i] 内的最高柱。
        leftMaximum[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMaximum[i] = Math.max(leftMaximum[i - 1], height[i]);
        }
        // rightMaximum[i] 保存区间 [i, n - 1] 内的最高柱。
        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)

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;
    }
}

边界与易错点

旧 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