# 42. Trapping Rain Water

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

## Ex

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.


Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9


## Constraints:

n == height.length

1 <= n <= 2 * 10^4

0 <= height[i] <= 10^5

# Solution 1: Max Left, Max Right So Far!

## 思路

A ith bar can trap the water if and only if there exists a higher bar to the left and a higher bar to the right of ith bar.

To calculate how much amount of water the ith bar can trap, we need to look at the maximum height of the left bar and the maximum height of the right bar, then

1) The water level can be formed at ith bar is: waterLevel = min(maxLeft[i], maxRight[i])

2) If waterLevel >= height[i] then ith bar can trap waterLevel - height[i] amount of water.

To achieve in O(1) when looking at the maximum height of the bar on the left side and on the right side of ith bar, we pre-compute it:

1) Let maxLeft[i] is the maximum height of the bar on the left side of ith bar.

2) Let maxRight[i] is the maximum height of the bar on the right side of ith bar.


1) ith 位置什么情况下可以存水？

2）ith 位置能存多少水呢？

ith 和水位线直接对比，如果小于水位线就可以存水。

## java 实现

/**
* @author d
* @since 1.0.0
*/
public class T042_TrappingRainWater {

/**
* 计算
*
* 1. 两个数组保存两边的高度
*
* 2. 循环计算
*
* @param height 高度
* @return 结果
*/
public int trap(int[] height) {
int n = height.length;

//1. 最大高低数组
int[] leftMax = new int[n];
int[] rightMax = new int[n];
//1.1 左边 从左到右
for(int i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i-1], leftMax[i-1]);
}
//1.2 右边 从右到左
for(int i = n-2; i >= 0; i--) {
rightMax[i] = Math.max(height[i+1], rightMax[i+1]);
}

//2. 遍历计算
int sum = 0;
for(int i = 0; i < n; i++) {
int waterLevel = Math.min(leftMax[i], rightMax[i]);

sum += Math.max(0,  waterLevel - height[i]);
}
return sum;
}

}


1ms, beats 99%。

TC: O(N), where N <= 3*10^4 is number of bars.

SC: O(N)

# Solution 2: Two Pointers

## 算法

Same idea with solution 1, but now we don't need to build maxLeft and maxRight arrays, we will calculate maxLeft and maxRight as we go.

We start with maxLeft = height[0], maxRight = height[n-1], using 2 pointers left point to the next bar on the left side, right point to the next bar on the right side.

How to decide to move left or move right?

If maxLeft < maxRight, it means the water level is based on the left side (the left bar is smaller) then move left side:
If height[left] > maxLeft then there is no trap water, we update maxLeft by maxLeft = height[left].
Else if height[left] < maxLeft then it can trap an amount of water, which is maxLeft - height[left].
Move left by left += 1

Else if maxLeft > maxRight, it means the water level is based on the right side (the right bar is smaller) then move right side:
If height[right] > maxRight then there is no trap water, we update maxRight by maxRight = height[right].
Else if height[right] < maxRight then it can trap an amount of water, which is maxRight - height[right].
Move right by right -= 1.


1) maxLeft 小于 maxRight

if(height[left] > maxLeft) {
// 无法蓄水
maxLeft = height[left];

} else {
// 可以蓄水
int water = maxLeft - height[left];
}

// 左边指针往右移动
left++;


2) maxLeft 大于 maxRight

if(height[right] > maxRight) {
// 无法蓄水
maxRight = height[right];
} else {
// 可以蓄水
int water = maxRight - height[right];
}

// 右边指针往左移动
right--;


## java 实现

/**
* @author d
* @since 1.0.0
*/
public class T042_TrappingRainWaterV2 {

/**
* 计算
*
* 1. 通过双指针，实时计算
*
* @param height 高度
* @return 结果
*/
public int trap(int[] height) {
int n = height.length;

//1. 最大高度
int left = 0;
int right = n-1;
int maxLeft = height[left];
int maxRight = height[right];

int sum = 0;
while (left <= right) {
// 取决于左边
if(maxLeft < maxRight) {
if(height[left] > maxLeft) {
// 无法蓄水
maxLeft = height[left];
} else {
// 可以蓄水
sum += maxLeft - height[left];
}

// 左边指针往右移动
left++;
} else {
// 取决于右边
if(height[right] > maxRight) {
// 无法蓄水
maxRight = height[right];
} else {
// 可以蓄水
sum += maxRight - height[right];
}

// 右边指针往左移动
right--;
}
}

return sum;
}

}


Complexity

TC: O(N), where N <= 3*10^4 is number of bars.

SC: O(1)

# 参考资料

https://leetcode.com/problems/trapping-rain-water/description/

https://leetcode.com/problems/trapping-rain-water/solutions/17357/sharing-my-simple-c-code-o-n-time-o-1-space/

https://leetcode.com/problems/trapping-rain-water/solutions/17391/share-my-short-solution/

https://leetcode.com/problems/trapping-rain-water/solutions/153992/java-o-n-time-and-o-1-space-with-explanations/

https://leetcode.com/problems/trapping-rain-water/solutions/1374608/c-java-python-maxleft-maxright-so-far-with-picture-o-1-space-clean-concise/