leetcode 42. 接雨水

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

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0 ;
        }
        int ans = 0;
        int[] leftmax = new int[height.length];
        int[] rightmax = new int[height.length];
        int n = height.length ;
        leftmax[0] = height[0] ;
        rightmax[n-1] = height[n-1] ;
        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 = 0 ; i < n ; i++){
            ans = ans + Math.min(leftmax[i] , rightmax[i]) - height[i] ;
        }
        return ans ;
        
    }
}