经典接雨水-刷题笔记

leetcode42

按行求（测试用例通过，但超时）

class Solution {
    public int trap(int[] height) {
    
        int res=0;
        int n=height.length;
        int maxh=0;
        for(int i=0;i<n;i++){
            maxh=Math.max(maxh,height[i]);
        }
        for(int row=1;row<=maxh;row++){
            int tmp=0;          
            int i=0;
            while(height[i++]<row);
            while(i<n){
                if(height[i]<row){
                    tmp++;
                }else{
                    res+=tmp;
                    tmp=0;
                }
                i++;
            }
        }
        return res;
    }
}

按列求（通过，耗时久）

class Solution {
    public int trap(int[] height) {
    
        int sum=0;
        for(int i=1;i<height.length-1;i++){
            int max_left=0;
            for(int j=i-1;j>=0;j--){   
                max_left=Math.max(max_left,height[j]);               
            }
            int max_right=0;
            for(int j=i+1;j<=height.length-1;j++){   
                max_right=Math.max(max_right,height[j]);               
            }
            sum+=Math.min(max_left,max_right)>height[i]?Math.min(max_left,max_right)-height[i]:0;
        }
        return sum;
    }
}

DP（快，按列求升级版）

class Solution {
    public int trap(int[] height) {

        int n=height.length;
        int[] leftMax=new int[n];
        int[] rightMax=new int[n];
        leftMax[0]=height[0];
        rightMax[n-1]=height[n-1];
        int res=0;
        for(int i=1;i<n;i++){
            leftMax[i]=Math.max(leftMax[i-1],height[i]);
        }

        for(int i=n-2;i>=0;i--){
            rightMax[i]=Math.max(rightMax[i+1],height[i]);
        }

        for(int i=1;i<n-1;i++){
            int lrMax=Math.min(leftMax[i-1],rightMax[i+1]);
            if(height[i]<lrMax){
                res+=lrMax-height[i];
            }
        }
        return res;
    }   
}