Trapping Rain Water
Two Pointers, Stack, Dynamic Programming
Hard
Question
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.
Trapping Rain Water
Example
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Challenge
O(n) time and O(1) memory
O(n) time and O(n) memory is also acceptable.
Tags
Two Pointers Forward-Backward Traversal Array
Related Problems
Medium Container With Most Water
Hard Trapping Rain Water II
Candy
Analysis
Reference: https://leetcode.com/articles/trapping-rain-water/
Brute Force
最直觉的想法就是对于每个bar，找到其左边和右边最大的bar height: leftMax, rightMax，再减去bar本身的高度heights[i]，就得到该处能存水的量。嵌套两重循环，每次只储存某个bar的左右最大height，因此
Time Complexity O(n^2), Space Complexity O(1)
Dynamic Programming
对于每一个bar来说，能装水的容量取决于左右两侧bar的最大值。扫描两次，一次从左向右，记录对于每一个bar来说其左侧的bar的最大高度left[i]，一次从右向左，记录每一个bar右侧bar的最大高度right[i]。第三次扫描，则对于每一个bar，计算
（1）左侧最大height和当前bar的height的差值（left[i] - heights[i]）
（2）右侧最大height和当前bar的height的差值（right[i] - heights[i]），
取（1），（2）中结果小的那个作为当前bar的蓄水量。最终求和得到总蓄水量。或者直接找到bari两侧最大height中最小的那个，再找与heights[i]的大于零的差值即可。
The water each bar can trap depends on the maximum height on its left and right. Thus scan twice - from left to right, and right to left and record the max height in each direction. The third time calculate the min difference between left/right height and current bar height. Sum the trapped water to get the final result.
简而言之：找左边最大和右边最大可以通过两个dp数组来存起来.
dpLeft[i] = Math.max(dpLeft[i - 1], height[i]); dpRight[i] = Math.max(dpRight[i + 1], height[i]);
Time: O(N), Space: O(2*N)
Two Pointers
@Grandyang: 我们来看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合。
Time: O(N), Space: O(1)
Monotonic Stack
@reeestart: 和largest rectangle in histogram一样的思路. 只不过histogram是用递增栈, 这道题是使用递减栈. stack里存的也是index.
每次出栈的时候是处理出栈的栈顶元素而非当前元素. 因为每次需要出栈的时候我们可以确定:
height[stk.peek()] < height[stk.peek().peek()], stk.peek().peek() 就是栈顶第二大的元素.
height[stk.peek()] < height[i]
Solution
Brute Force
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int ans = 0;
for (int i = 0; i < height.length; i++) {
int leftMax = 0;
int rightMax = 0;
int j = i - 1;
int k = i + 1;
int waterHeight = 0;
while (j >= 0) {
leftMax = Math.max(height[j], leftMax);
j--;
}
while (k < height.length) {
rightMax = Math.max(height[k], rightMax);
k++;
}
waterHeight = Math.min(leftMax, rightMax);
ans += Math.max(waterHeight - height[i], 0);
}
return ans;
}
}Dynamic Programming
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
if (heights == null || heights.length < 3) {
return 0;
}
int length = heights.length;
int[] left = new int[length];
int[] right = new int[length];
int trapped = 0;
// For heights[0] or heights[length - 1], the max left/right height is 0
left[0] = 0;
right[length - 1] = 0;
// Keep track of the max height on the left of height[i]
for (int i = 1; i < length; i++) {
left[i] = Math.max(left[i - 1], heights[i - 1]);
}
// Keep track of the max height on the right of height[i]
for (int j = length - 2; j >= 0; j--) {
right[j] = Math.max(right[j + 1], heights[j + 1]);
}
// Calculate the total trapped water
for (int k = 0; k < length; k++) {
trapped += Math.max(Math.min(left[k], right[k]) - heights[k], 0);
}
return trapped;
}
}Two Pointers
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int leftMax = 0, rightMax = 0;
int left = 0, right = height.length - 1;
int trapped = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
trapped += Math.max(leftMax - height[left], 0);
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
trapped += Math.max(rightMax - height[right], 0);
}
right--;
}
}
return trapped;
}
}Monotonic Stack
class Solution {
public int trap(int[] height) {
int n = height.length;
Stack<Integer> stk = new Stack<>();
int res = 0;
for (int i = 0; i < n; i++) {
if (stk.isEmpty() || height[i] < height[stk.peek()]) {
stk.push(i);
} else {
while (!stk.isEmpty() && height[i] >= height[stk.peek()]) {
int h = height[stk.pop()];
if (!stk.isEmpty()) {
int len = i - stk.peek() - 1;
res += (Math.min(height[i], height[stk.peek()]) - h) * len;
}
}
stk.push(i);
}
}
return res;
}
}Reference
Last updated
Was this helpful?