> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/42.-trapping-rain-water.md).

# 42. Trapping Rain Water

## problem 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.

![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)\
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
```

## algorithm thought

和之前一个接水的题目异曲同工，使用左右指针结题。哪边短，动哪边，最后两指针重合退出循环。中间维护左右相应的最大值，存水量等于最大值减去当前值。

## code

```
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()==0)
            return 0;
        int left=0;
        int right=height.size()-1;
        int leftmax=height[left];
        int rightmax=height[right];
        int res=0;
        while(left<right){
           // cout<<left<<'-'<<right<<' ';
            if(height[left]<height[right]){
                
                if(height[left]<=leftmax){
                    res+=leftmax-height[left++];
                }else{
                    leftmax=height[left];
                }
                
            }else{
                
                if(height[right]<=rightmax){
                    res+=rightmax-height[right--];
                }else{
                    rightmax=height[right];
                }
                
            }
        }
        return res;
    }
};
```

## algorithm thought

一个循环左右指针逼近，时间复杂度O(n)。