LeetCode - Trapping Rain Water
Problem description
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.
Example:
1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Analysis
One essential point is that we can iterate the whole array and add the area by maxHeight - height[i], then we can use two pointers from start and end of the array to find a max value and then we can use the formula to find out the answer.
Here’s the code, a detailed explanation:
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
public class TrappingRainWater {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
ans += (left_max - height[left]);
}
++left;
} else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
ans += (right_max - height[right]);
}
--right;
}
}
return ans;
}
}
What to improve
- when facing area, think it as multiple columns