leetcode-面试经典150题-42-接雨水（双指针c++）

第一遍做的时候（没有看题解）我想到的思路就是遍历每一个凹下去的部分，计算能接到的雨水数量，然后累加，left,right分别是凹点的左右边界

下面是代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        int ans=0;
        for(int i=1;i<=n-2;++i)
        {
            int left=i;
            int right=left;
            bool left_flag=false;
            bool right_flag=false;
            while(left>0)//在左边找大于height[i]的能接住雨水，
            {
                left--;
                if(height[i]<height[left])
                {
                    left_flag=true;
                    break;
                }
            }
            while(right<n-1)//在右边找能接到雨水的
            {
                right++;
                if(height[i]<height[right])
                {
                    right_flag=true;
                    break;
                }
            }
            //进行雨水计算，如果左右边界都有的话
            if(left_flag && right_flag)
            {
                int rain=min(height[left],height[right]);//能接到的雨水最大值，两个边界中的较小值
                int temp=(right-left-1)*rain;//
                for(int j=left+1;j<=right-1;++j)
                {
                    temp-=height[j];//减去高度值
                    height[j]=rain;//接到雨水后重新赋值
                }
                ans+=temp;
                i=right-1;//直接跳到right-1，能节省一些时间，
            }
        }
        return ans;
    }
};

就是时间有点慢，只有5%的击败，是自己独立解出hard题，写一下纪念一下。