share my 11 lines short cpp code,O(n) time ,O(1) space


  • 0
    Z
    int trap(vector<int>& height) {
            int lo=0,hi=height.size()-1,lomax=0,himax=0,ret=0,t;
            while(lo<=hi){
                lomax=max(lomax,height[lo]);
                himax=max(himax,height[hi]);
                if(lomax<=himax){
                    t=min(lomax,himax)-height[lo++];
                }
                else t=min(lomax,himax)-height[hi--];
                ret+=t>0?t:0;
            }
            return ret;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.