public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0 || height.length == 1) return 0;
        //对于每个 i 能盛水的量取决于左右两端高度的最小值  vol［i］＝min(left[i],right[i]) - height[i]
        // 遍历两次得到最高右板和最高左板 left［］，right［］ 在遍历一次计算。
        int left[] =new int[height.length];
        int right[] = new int[height.length];
        
        //得到每个index的右最高板
        left[0] = height[0];
        int maxl = left[0];
        for(int i = 1; i < height.length; i++){
            left[i] = Math.max(maxl, height[i]);
            maxl = Math.max(maxl, height[i]);
        }
        
        //得到每个index的左最高板
        right[height.length-1] = height[height.length-1];
        int maxr = height[height.length-1];
        for(int i = height.length-2 ; i>=0; i--){
            right[i] = Math.max(maxr, height[i]);
            maxr = Math.max(maxr, height[i]);
        }
        
        int vol = 0;
        for(int i = 1 ; i < height.length-1 ; i++){
            int bit = Math.min(left[i], right[i]) - height[i];
            if(bit > 0) vol += bit;
        }
        return vol;
    }
}