kniost

谁怕，一蓑烟雨任平生

0%

LeetCode 42. Trapping Rain Water

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟
LeetCode 42. Trapping Rain Water

42. Trapping Rain Water

Difficulty:: Hard

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


The above elevation map 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. Thanks Marcos for contributing this image!

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

Language: Java

算法核心是：一个坐标能累积的水等于左右两边的最高值取小的那个，减去本坐标的高度。可以通过记录每个点的左右来加速这一过程（DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int size = height.length;
        int[] leftMax = new int[size];
        leftMax[0] = height[0];
        int[] rightMax = new int[size];
        rightMax[size - 1] = height[size - 1];
        for (int i = 1, j = size - 2; i < size; i++, j--) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            rightMax[j] = Math.max(rightMax[j + 1], height[j]);
        }
        int result = 0;
        for (int i = 1; i < size - 1; i++) {
            result += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;
    }
}

单调栈解法

单调递减栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int result = 0;
        stack.push(-1);
        for (int i = 0; i < height.length; i++) {
            while (stack.peek() != -1 && height[i] >= height[stack.peek()]) {
                int low = height[stack.pop()];
                if (stack.peek() == -1) {
                    break;
                }
                int minHeight = Math.min(height[i], height[stack.peek()]);
                result += (minHeight - low) * (i - stack.peek() - 1);
            }
            stack.push(i);
        }
        return result;
    }
}

从小往大灌水解法

思想是左右指针各当成一根柱子，并记录左右最高的柱子，每次向中间移动小的那一根指针，如果发现新的柱子比原来的柱子矮，那么是可以灌水的，否则是不能灌水的并更新新的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int res = 0;
        int left = 0, right = height.length - 1;
        int leftHeight = height[left];
        int rightHeight = height[right];
        while(left < right) {
            if (leftHeight < rightHeight) {
                left++;
                if (height[left] < leftHeight) {
                    res += leftHeight - height[left];
                } else {
                    leftHeight = height[left];
                }
            } else {
                right--;
                if (height[right] < rightHeight) {
                    res += rightHeight - height[right];
                } else {
                    rightHeight = height[right];
                }
            }
        }
        return res;
    }
}