Simple Java O(n) time O(n) space solution


  • 0
    K

    public class Solution {
    // [0,1,0,2,1,0,1,3,2,1,2,1]
    // lmax (left -> right) [0,1,1,2,2,2,2,3,3,3,3,3]
    // rmax (right -> left) [3,3,3,3,3,3,3,3,2,2,2,1]

    // left -> right 
    // sum1: (sum(lmax - height))   0+1+1+0+1+2+1+0+1+2+1+2 = 11
    
    // right -> left 
    // sum2:   for lmax > rmax
    //         (sum(lmax - rmax))   2+1+1+1+stop = 5
    
    // vol = sum1 - sum2
    
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int len = height.length;
        int vol = 0;
        
        
        int[] lmax = new int[len];
        lmax[0] = height[0];
        
        for (int i = 1; i < len; i++) {
            lmax[i] = Math.max(lmax[i - 1], height[i]);
            vol += lmax[i] - height[i];
        }
    
        int[] rmax = new int[len];
        rmax[len - 1] = height[len - 1];
        
        for (int i = len - 1; i > 0; i--) {
            if (rmax[i] < lmax[i]) {
                vol -= lmax[i] - rmax[i];
            } else {
                return vol;
            }
            rmax[i - 1] = Math.max(rmax[i], height[i - 1]);
        }
    
        return vol;
    }
    

    }


Log in to reply
 

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