leetcode接雨水 trapping rain water 使用双指针

原文链接:https://leetcode-cn.com/problems/two-sum/solution/jie-yu-shui-by-leetcode/

和方法2相比,我们不从左和从右分开计算,我们想办法一次完成遍历。

从动态编程方法的示意图中我们注意到,只要right_max[i]>left_max[i],即右部的最大值大于左部的最大值,积水高度将有left_max决定,类似的只要left_max[i]>right_max[i],即左部的最大值大于右部的最大值,积水高度将由right_max决定。

所以我们可以认为如果一端有更高的条形块,例如右端,积水的高度依赖于当前方向的高度(从左到右)。当我们发现另一侧(右侧)的条形块高度不是最高的,我们则开始从相反的方向遍历(从右到左)。

我们必须在遍历时维护left_max和right_max,但是我们现在可以使用两个指针交替进行,实现1次遍历完成即可。


我们必须在遍历时维护 \text{left\_max}left_max 和 \text{right\_max}right_max ,但是我们现在可以使用两个指针交替进行,实现 1 次遍历即可完成。

算法:

int trap(int A[],int n){
        if(n<0){return 0;}
        int ans=0;
        int left_max=0,right_max=0;
        int left=0,right=n-1;
        while(left<right){
            if(A[left]<A[right]){//说明左边比右边小,这个时候应该从左边开始计算
                if(A[left]>=left_max){left_max=A[left];}
                else{ans+=left_max-A[left];}
                left++;
            }else{
                if(A[right]>=right_max){right_max=A[right];}
                else{ans+=right_max-A[right];}
                right--;
            }
        }
        return ans;
    }


链接:https://leetcode-cn.com/problems/two-sum/solution/jie-yu-shui-by-leetcode/
 

上一篇:A water problem HDU - 5832(大数)


下一篇:trapping-rain-water