LeetCode 42. Trapping Rain Water
LeetCode 42. Trapping Rain Water
LINK: https://leetcode.com/problems/trapping-rain-water/description/
Matter
You are given an array where each value represents the height of a vertical bar.
After rain falls, water can be trapped between taller bars.
Return the total amount of water that can be stored.
Example.
[1]
Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output:
6
Explanation:
Water is trapped between higher bars, and the total amount is 6.
[2]
Input:
height = [4,2,0,3,2,5]
Output:
9
Explanation:
Several lower areas are surrounded by taller bars, so they can hold water.
Constraints
1 <= height.length <= $2 \times 10^4$
0 <= height[i] <= $10^5$
Problem analysis
For each position, the amount of trapped water depends on the tallest bar on its left side and the tallest bar on its right side.
The water level at index i is limited by the smaller one between those two values.
1
water = min(left_max, right_max) - height[i]
Solution
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
27
28
29
30
31
32
33
34
35
#include <vector>
class Solution {
public:
int trap(std::vector<int>& height)
{
int i32LeftIdx = 0;
int i32RightIdx = (int)height.size() - 1;
int i32LeftH = height[0];
int i32RightH = height[i32RightIdx];
int i32LeftMaxH = i32LeftH;
int i32RightMaxH = i32RightH;
int i32TrapWater = 0;
while(i32LeftIdx < i32RightIdx)
{
if(i32LeftH < i32RightH)
{
i32LeftMaxH = std::max(i32LeftMaxH, i32LeftH);
i32TrapWater += i32LeftMaxH - i32LeftH;
i32LeftIdx++;
i32LeftH = height[i32LeftIdx];
}
else
{
i32RightMaxH = std::max(i32RightMaxH, i32RightH);
i32TrapWater += i32RightMaxH - i32RightH;
i32RightIdx--;
i32RightH = height[i32RightIdx];
}
}
return i32TrapWater;
}
};