lintcode刷题——接雨水

原题如下：

接雨水 

•  描述
•  笔记
•  数据
•  评测

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.

您在真实的面试中是否遇到过这个题？  Yes 样例

如上图所示，海拔分别为 

[0,1,0,2,1,0,1,3,2,1,2,1]

, 返回 

6

.

做题思路：

1、每一个点能接的雨水就是其左右最大值中的较小的一个减去该点的海拔高度；

2、两根指针往中间走，对比当前的海拔高度的值，取较小的一个减去该点的海拔高度，指针移动。

具体的C++代码如下所示：

class Solution {

public:

    int trapRainWater(vector<int> heights) {

        // write your code here

        int len=heights.size();

        if(len==0)

        return 0;

        int i=0,j=len-1;

        int w=0;

        int lmax=0,rmax=0;

        while(i<j)

        {

           lmax=max(heights[i],lmax);

           rmax=max(heights[j],rmax);

           if(lmax<rmax)

           {

               w+=lmax-heights[i];//取左右最大值小的

               i++;

           }

           else

           {

              w+=rmax-heights[j];

              j--;

           }

        }

       return w;

    }

};