0042. 接雨水 [Hard] [Trapping Rain Water].md

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 is able to trap after raining.

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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

---

题目：

思路：双指针，参考Discuss。当height[l] < height[r]时，如果l到r之间的高度均为0时，其能装满的雨水的量由高度低的一端决定。转换求解每个柱能装的雨水量。用left_max记录height[0...l-1]的最大值，如果height[l] < height[r]，此时height[l]若比left_max小，那么我们可以得到height[l]能够装满的雨水量为min(left_max, height[r]) - height[l]，（此时的height[r] >= left_max）然后右移左指针。同理当右指针左移时同样进行判断。

工程代码下载

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;

        int res = 0;
        int left_max = 0, right_max = 0;
        while(l <= r){
            if(height[l] <= height[r]){
                if(height[l] > left_max)
                    left_max = height[l];
                else
                    res += left_max - height[l];
                l += 1;
            }
            else{
                if(height[r] > right_max)
                    right_max = height[r];
                else
                    res += right_max - height[r];

                r -= 1;
            }
        }
        return res;
    }
};