42. Trapping Rain Water

最新推荐文章于 2024-01-03 14:36:13 发布

coding_ironboy

最新推荐文章于 2024-01-03 14:36:13 发布

阅读量89

点赞数

本文链接：https://blog.csdn.net/coding_ironboy/article/details/101037852

版权

    int trap(vector<int>& height) {
        int leftmax=0,rightmax=0,res=0;
        int lf=0,rh=height.size()-1;
        while(lf<rh){
            if(height[lf]<height[rh]){
                leftmax=max(leftmax,height[lf]);
                res+=leftmax-height[lf++];
            }
            else{
                rightmax=max(rightmax,height[rh]);
                res+=rightmax-height[rh--];
            }
        }
        return res;
    }

双指针方法，主要还是理解题意。

也可以用dp。