【刷题篇】接雨水(一维)

一、题目

OJ链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

二、题解

2.1思路

2.2源码

 public int trap(int[] height) {
    
        if(height==null||height.length<2){
    
            return 0;
        }
        int N=height.length;
        int leftMax=height[0];
        int rightMax=height[N-1];
        int L=1;
        int R=N-2;
        int water=0;
        while(L<=R){
    
            if(leftMax<=rightMax){
    
                water+=Math.max(0,leftMax-height[L]);
                leftMax=Math.max(leftMax,height[L++]);
            }else {
    
                water+=Math.max(0,rightMax-height[R]);
                rightMax=Math.max(rightMax,height[R--]);
            }
            
        }
        return water;
    }