接雨水

发表于 更新于 分类于 本文字数： 480 阅读时长 ≈ 5 分钟

题目描述

Leetcode题目：42. 接雨水

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

1
2
3
4
5
6
7
输入：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

解题思路

  1. 暴力解法。唯有山谷可以接住雨水，接住雨水的大小等于左右两边的山峰（left、right）
    更低的一边，与谷底（当前值）的差值，依次累加
  2. 双指针优化。解法1也是双指针，但是有重复的取left、right最大值，优化思路，
    使用数组保存当前值的left、right最大值。
  3. 栈思路。栈保存数组索引，栈头表示当前值，栈头第二个表示left左侧，需要比较的为right

代码

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int trap(int[] height) {
    int len = height.length;
    int res = 0;
    for (int i = 1; i < len - 1; i++) {
        int left = height[i];
        int right = height[i];
        for (int j = i + 1; j < len; j++) {
            if (height[j] > right) {
                right = height[j];
            }
        }
        for (int j = i - 1; j >= 0; j--) {
            if (height[j] > left) {
                left = height[j];
            }
        }
        int temp = Math.min(left, right) - height[i];
        res += temp;
    }
    return res;
}

双指针优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int trap2(int[] height) {
    int len = height.length;
    int res = 0;
    int[] lefts = new int[len];
    int[] rights = new int[len];

    lefts[0] = height[0];
    for (int i = 1; i < len; i++) {
        lefts[i] = Math.max(height[i], lefts[i - 1]);
    }

    rights[len - 1] = height[len - 1];
    for (int i = len - 2; i >= 0; i--) {
        rights[i] = Math.max(height[i], rights[i + 1]);
    }

    for (int i = 0; i < len; i++) {
        res += Math.min(lefts[i], rights[i]) - height[i];
    }
    return res;
}

栈思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int trap3(int[] height) {
    int len = height.length;
    int res = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1; i < len; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int cur = stack.pop();
            if (!stack.isEmpty()) {
                int h = Math.min(height[stack.peek()], height[i]) - height[cur];
                int w = i - stack.peek() - 1;
                res += h * w;
            }
        }
        stack.push(i);
    }
    return res;
}

项目地址