# 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:*
### 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的蓄水量。最终求和得到总蓄水量。或者直接找到bar`i`两侧最大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.
[简而言之](http://reeestart.me/2019/01/02/LeetCode-42-Trapping-Rain-Water/)：找左边最大和右边最大可以通过两个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](http://www.cnblogs.com/grandyang/p/4402392.html): 我们来看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合。
Time: O(N), Space: O(1)
### Monotonic Stack
[@reeestart](http://reeestart.me/2019/01/02/LeetCode-42-Trapping-Rain-Water/): 和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
```java
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
```java
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
```java
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
```java
class Solution {
public int trap(int[] height) {
int n = height.length;
Stack 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
* [LeetCode Article Solution: Trapping Rain Water](https://leetcode.com/articles/trapping-rain-water/)
* [Trapping Rain Water - GeeksforGeeks](https://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/two_pointers/www.geeksforgeeks.org/trapping-rain-water/README.md)
* [LeetCode – Trapping Rain Water (Java) - Program Creek](https://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/two_pointers/www.programcreek.com/2014/06/leetcode-trapping-rain-water-java/README.md)
* [喜刷刷: LeetCode - Trapping Rain Water](https://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/two_pointers/bangbingsyb.blogspot.com/2014/11/leetcode-trapping-rain-water.html)
* [Yu's Garden LeetCode Question 111: Trapping Rain Water](http://yucoding.blogspot.com/2013/05/leetcode-question-111-trapping-rain.html)
* [水中的鱼：Trapping Rain Water 解题报告](http://fisherlei.blogspot.com/2013/01/leetcode-trapping-rain-water.html)