WangBa's Blog

0042. Trapping Rain Water

LeetCode真的难系列

发布于：2020年10月28日
次浏览

42. Trapping Rain Water Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

img

1
2
3
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

1
2
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

思路：

思路一：行求解

每次求一行的所有水：

  • 首先要标记是否开始，只要第一次出现 height[i] >= 当前层次的值时，才开始计数，因为它左边没有墙

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int trap(int[] height) {
    // find the maximum num in the height
    int max = Integer.MIN_VALUE;
    for (int i : height) {
        if (i > max) max = i;
    }
    int res = 0;
    for (int i = 1; i <= max; i++) {
        int count = 0;
        boolean start = false;
        for (int value : height) {
            if (start && value < i) {
                count++;
            }

            if (value >= i) {
                res += count;
                count = 0;
                start = true;
            }
        }
    }
    return res;
}

时间复杂度：O(n * m) 其中 n 为数组长度，m 为数组中最大的值

空间复杂度：O(1)

思路二：列求解

  • 只要关注于每一列就行，且关注该列的左边最高列和右边最高列
  • 如何求解该列的水，只需要将这左右高列中较低的那个减去当前的列的高度即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int trap(int[] height) {
    // 2. column
    int count = 0;
    for (int i = 0; i < height.length; i++) {
        int minColumn = getMinColumn(i, height);
        if (minColumn > height[i]) {
            count += (minColumn - height[i]);
        }
    }
    return count;
}

private int getMinColumn(int index, int[] height) {
    int left = 0, right = 0;
    for (int i = 0; i < index; i++) {
        if (height[i] > left) left = height[i];
    }
    for (int i = index + 1; i < height.length; i++) {
        if (height[i] > right) right = height[i];
    }
    return Math.min(left, right);
}

时间复杂度：O(n^2)

空间复杂度：O(1)

思路三：栈

可以想象为括号匹配：其中墙可以看作括号，水可以看作括号匹配的中间计算

代码：

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

思路四：动态规划

在思路二中，是使用没次找一个数，都要遍历整个数组找到左边和右边的最高列，然后进行计算，在这个基础上，使用一个 dp 数组将这些值维护起来：

第 i 列的左边最高列和右边最高列应该为：

left[i] = max(left[i - 1], height[i - 1])

right[i] = max(right[i + 1], height[i + 1])

这样用两个数组去维护就行了，每次遍历的时候直接在这个 dp 数组中取就行了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int trap(int[] height) {
    int res = 0;
    int[] left = new int[height.length];
    int[] right = new int[height.length];

    // use array to save the maximum left num of every item
    for (int i = 1; i < height.length - 1; i++) {
        left[i] = Math.max(left[i - 1], height[i - 1]);
    }

    // use array to save the maximum right num of every item
    for (int i = height.length - 2; i >= 0; i--) {
        right[i] = Math.max(right[i + 1], height[i + 1]);
    }

    for (int i = 0; i < height.length; i++) {
        int minColumn = Math.min(left[i], right[i]);
        if (minColumn > height[i]) {
            res += minColumn - height[i];
        }
    }
    return res;
}

时间复杂度：O(n）

空间复杂度：O(n)

思路五：动态规划 + 双指针

在思路四中，已经使用 dp 数组去存储左边和右边的最高列，但是仔细思考一下，这个 dp 数组中的值，其实就使用一次，那么可以将这个空间复杂度再降低一点，有点类似于用动态规划求解斐波那契数列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int trap(int[] height) {
    int res = 0, l = 0, r = height.length - 1;
    while (l < r) {
        int mn = Math.min(height[l], height[r]);
        if (height[l] == mn) {
            ++l;
            while (l < r && height[l] < mn) {
                res += mn - height[l++];
            }
        } else {
            --r;
            while (l < r && height[r] < mn) {
                res += mn - height[r--];
            }
        }
    }
    return res;
}

时间复杂度：O(n）

空间复杂度：O(1)

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/28/0042-Trapping-Rain-Water/

更新于：2020年10月30日

Leetcode

Stack

评论