Trapping Rain Water

LeetCode #42

Description:

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.

Example:

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Idea:

1. 先从左往右过一遍，找出每个柱子左边最大的值。
2. 再从右往左过一遍，找出每个柱子右边最大的值。
3. 再过一遍，利用左右最大值求每个位置能存的水，update一共能存的水。

Time O(n), Space O(n) 要存左右最大值。

Code:

class Solution {
public:
    int trap(vector<int>& height) {
        int len=height.size();
        if(len<=2) return 0;

        vector<int> left_high(len);
        vector<int> right_high(len);

        int left_highest=height[0];
        for(int i=0; i<len; ++i){
            left_high[i] = left_highest;
            left_highest = max(height[i], left_highest);
        }

        int right_highest=height[len-1];
        for(int i=len-1; i>=0; --i){
            right_high[i] = right_highest;
            right_highest = max(height[i], right_highest);
        }

        int sum_water=0;
        for(int i=0; i<len; ++i){
            int bound_height=min(left_high[i],right_high[i]);
            if(bound_height>height[i]) sum_water += bound_height - height[i];
        }

        return sum_water;
    }
};