和方法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/