42 Trapping Rain Water

1. Question

Givennnon-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.
For example, Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

2. Implementation

(1) Two Pointers
1
class Solution {
2
public int trap(int[] height) {
3
if (height == null || height.length <= 1) {
4
return 0;
5
}
6
7
int left = 0, right = height.length - 1;
8
int leftMaxHeight = height[left], rightMaxHeight = height[right];
9
int res = 0;
10
11
while (left < right) {
12
if (height[left] < height[right]) {
13
++left;
14
leftMaxHeight = Math.max(leftMaxHeight, height[left]);
15
res += leftMaxHeight - height[left];
16
}
17
else {
18
--right;
19
rightMaxHeight = Math.max(rightMaxHeight, height[right]);
20
res += rightMaxHeight - height[right];
21
}
22
}
23
return res;
24
}
25
}
Copied!
(2) Monotone Stack
思路:(1) 凹陷处可以积水。所以寻找先递减后递增的位置就可以了
(2) 维护一个单调递减的Stack,当heights[stack.peek()] <= heights[i], 找到凹陷处,出栈,计算可蓄水的体积
(3) 计算体积时,以bottomIndex作为中点,向两边找出比它高的bar(corner case: 如果此时stack为空,则无法找到左边的bar)
1
class Solution {
2
public int trap(int[] height) {
3
Stack<Integer> stack = new Stack<>();
4
int res = 0, water = 0;
5
6
for (int i = 0; i < height.length; i++) {
7
while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
8
int bottomIndex = stack.pop();
9
10
if (stack.isEmpty()) {
11
water = 0;
12
}
13
else {
14
int width = i - stack.peek() - 1;
15
int h = Math.min(height[stack.peek()], height[i]) - height[bottomIndex];
16
water = width * h;
17
}
18
res += water;
19
}
20
stack.push(i);
21
}
22
return res;
23
}
24
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)
Monotone Stack: 时间复杂度O(n), 空间复杂度O(n)