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.

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

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!

题目大意

给定一系列的非负整数，把他们看成坐标轴上的数，如上图所示，黑色的就是用数字围成的墙，求这个容器可以装下多少水，也就是蓝色的部分可以有多少.

代码

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

解答

使用twopoint的思想，(使用twopoint的时候，貌似循环条件都是left<right 或者left<= right吧。。。)

首先应该知道，每个Bar上装的水的量取决于 左边最高的Bar和右边最高的bar中的较小值。

用left和right来指向本次循环处理哪个Bar（两边是交替着进行的，不像一个循环一样从左到右进行循环）, leftmax和rightmax 分别来记录左边最大的Bar和右边最大的bar。