每日算法 — 使用java实现接雨水：双指针贪心与单调栈优化

问题描述

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

示例：

输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

算法思路分析

方法一：暴力解法

对于每个位置，找到其左边最高和右边最高的柱子，该位置能接的雨水量为 min(maxLeft, maxRight) - height[i]。时间复杂度 O(n²)。

方法二：动态规划（预处理最值）

预先计算每个位置的左边最大值和右边最大值数组，将查询优化到 O(1)，总时间复杂度 O(n)，空间复杂度 O(n)。

方法三：双指针（最优空间）

维护左右两个指针和左右两边的最大高度。哪边的最大高度较小，就先处理哪边。时间复杂度 O(n)，空间复杂度 O(1)。

方法四：单调栈

利用单调递减栈，当遇到更高的柱子时，弹出栈顶计算凹槽中的雨水量。可同时计算多个凹槽。

Java 完整实现

import java.util.ArrayDeque;
import java.util.Deque;

public class TrappingRainWater {

    /**
     * 方法一：动态规划（预处理左右最大值）
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    public int trapDP(int[] height) {
        if (height == null || height.length < 3) return 0;
        int n = height.length;

        // leftMax[i] 表示位置 i 左侧（含 i）的最高柱子高度
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // rightMax[i] 表示位置 i 右侧（含 i）的最高柱子高度
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 每个位置接水量 = min(左最高, 右最高) - 当前高度
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return water;
    }

    /**
     * 方法二：双指针（空间优化版）
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    public int trapTwoPointers(int[] height) {
        if (height == null || height.length < 3) return 0;
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                // 左边较小，以 leftMax 为瓶颈计算
                if (height[left] >= leftMax) {
                    leftMax = height[left]; // 更新左边最大
                } else {
                    water += leftMax - height[left]; // 可以接水
                }
                left++;
            } else {
                // 右边较小（或相等），以 rightMax 为瓶颈计算
                if (height[right] >= rightMax) {
                    rightMax = height[right]; // 更新右边最大
                } else {
                    water += rightMax - height[right]; // 可以接水
                }
                right--;
            }
        }
        return water;
    }

    /**
     * 方法三：单调栈
     * 时间复杂度：O(n)，空间复杂度：O(n)
     * 栈中保存的是柱子的下标，对应高度单调递减
     */
    public int trapMonotonicStack(int[] height) {
        if (height == null || height.length < 3) return 0;
        int n = height.length;
        Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈
        int water = 0;

        for (int i = 0; i < n; i++) {
            // 当前柱子比栈顶高，可以形成凹槽接水
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = stack.pop(); // 凹槽底部
                if (stack.isEmpty()) break; // 没有左边界

                int left = stack.peek(); // 左边界下标
                // 凹槽宽度 = 当前下标 - 左边界下标 - 1
                int width = i - left - 1;
                // 凹槽高度 = min(左边界高度, 右边界高度) - 底部高度
                int h = Math.min(height[left], height[i]) - height[bottom];
                water += width * h;
            }
            stack.push(i);
        }
        return water;
    }

    /**
     * 扩展：接雨水 II（三维版本，接雨水II）
     * 使用优先队列（最小堆）从边界向内部扩展
     */
    public int trapRainWaterII(int[][] heightMap) {
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }
        int rows = heightMap.length;
        int cols = heightMap[0].length;
        boolean[][] visited = new boolean[rows][cols];

        // 最小堆：按高度排序，存储 (高度, 行, 列)
        java.util.PriorityQueue<int[]> minHeap = new java.util.PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );

        // 将边界加入堆
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    minHeap.offer(new int[]{heightMap[i][j], i, j});
                    visited[i][j] = true;
                }
            }
        }

        int water = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxBoundary = 0;

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int h = curr[0], r = curr[1], c = curr[2];
            maxBoundary = Math.max(maxBoundary, h);

            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) {
                    continue;
                }
                visited[nr][nc] = true;
                // 如果内部格子低于当前边界，可以蓄水
                if (heightMap[nr][nc] < maxBoundary) {
                    water += maxBoundary - heightMap[nr][nc];
                }
                minHeap.offer(new int[]{heightMap[nr][nc], nr, nc});
            }
        }
        return water;
    }

    /**
     * 可视化：打印每个位置的接水量
     */
    public void visualize(int[] height) {
        if (height == null || height.length == 0) return;
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

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

        System.out.println("高度图:  " + java.util.Arrays.toString(height));
        int[] water = new int[n];
        for (int i = 0; i < n; i++) {
            water[i] = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        System.out.println("接水量:  " + java.util.Arrays.toString(water));
    }

    public static void main(String[] args) {
        TrappingRainWater solution = new TrappingRainWater();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        System.out.println("=== 接雨水问题 ===");
        solution.visualize(height);

        System.out.println("\nDP 解法: " + solution.trapDP(height.clone()));
        System.out.println("双指针解法: " + solution.trapTwoPointers(height.clone()));
        System.out.println("单调栈解法: " + solution.trapMonotonicStack(height.clone()));

        // 测试三维接雨水
        int[][] heightMap = {
            {1, 4, 3, 1, 3, 2},
            {3, 2, 1, 3, 2, 4},
            {2, 3, 3, 2, 3, 1}
        };
        System.out.println("\n接雨水 II (三维): " + solution.trapRainWaterII(heightMap));
    }
}

复杂度分析

扩展思考

1. 最大蓄水量：给定 n 根柱子，选择两根作为边界，使它们之间的蓄水量最大（双指针经典题）。
2. 接雨水 II：二维地形接雨水，需要使用优先队列从边界向内部渗透。
3. 动态添加柱子：如果柱子高度可以动态变化，需要维护数据结构快速查询。

总结

接雨水问题是理解双指针贪心策略的绝佳案例。双指针解法的精妙之处在于：每次移动较短的一边，因为接水量由较短的边界决定。单调栈版本则展示了如何用栈结构处理”寻找下一个更大元素”类问题。从二维到三维的扩展，更体现了算法思维在不同维度间的迁移能力。