# C++[LeetCode][DP] Trapping Rain Water

## Problem

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.

For example,
Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`.

Water

The above elevation map 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.

## Solution

• 当下因素高度。

Swift

``````class Solution {
func trap(height: [Int]) -> Int {
if height.count == 0 {
return 0
}
var leftMax: [Int] = []
var rightMax: [Int] = []
var maxH = -1
for h in height {
leftMax.append(maxH)
maxH = max(maxH, h)
}
maxH = -1
for h in height.reverse() {
rightMax.insert(maxH, atIndex: 0)
maxH = max(maxH, h)
}

var ret : Int = 0
for i in 0..<leftMax.count {
let h = min(leftMax[i], rightMax[i])
let water = max(0, h - height[i])
ret += water
}

return ret
}
}
``````

Swift

``````class Solution {
func trap(height: [Int]) -> Int {
if height.count == 0 {
return 0
}
var i = 0
var j = height.count - 1
var ret = 0
var leftHeight = height
var rightHeight = height[j]
while i < j {
let minHeight = min(leftHeight, rightHeight)
if (leftHeight < rightHeight) {
i += 1
let water = max(minHeight - height[i], 0)
ret += water
leftHeight = max(leftHeight, height[i])
} else {
j -= 1
let water = max(minHeight - height[j], 0)
ret += water
rightHeight = max(rightHeight, height[i])
}
}

return ret
}
}
``````

C++

``````class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
if (heights.size() == 0) {
return 0;
}
int i = 0;
int j = heights.size() - 1;
int leftHeight = heights[i];
int rightHeight = heights[j];
int ret = 0;
while (i < j) {
int minHeight = min(leftHeight, rightHeight);
if (leftHeight < rightHeight) {
i++;
int water = max(minHeight - heights[i], 0);
ret += water;
leftHeight = max(leftHeight, heights[i]);
} else {
j--;
int water = max(minHeight - heights[j], 0);
ret += water;
rightHeight = max(rightHeight, heights[j]);
}
}
return ret;
}
};
``````