O(n) time O(n) space DP Java Solution, and O(n) time O(1) space Java Solution


  • 0
    public int trap(int[] height) {
        int result = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            left[i] = (i == 0 || height[i] > left[i - 1]) ? height[i] : left[i - 1];
        }
        for (int i = height.length - 1; i >= 0; i--) {
            right[i] = (i == height.length - 1 || height[i] > right[i + 1]) ? height[i] : right[i + 1];
        }
        for (int i = 0; i < height.length; i++) {
            result += Math.max(0, Math.min(left[i], right[i]) - height[i]); 
        }
        return result;
    }
    
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        int leftMax = height[left];
        int rightMax = height[right];
        while (left < right) {
            if (height[left] < height[right]) {
                result += Math.max(0, leftMax - height[left]);
                leftMax = Math.max(leftMax, height[left]);
                left++;
            } else {
                result += Math.max(0, rightMax - height[right]);
                rightMax = Math.max(rightMax, height[right]);
                right--;
            }
        }
        return result;
    }

Log in to reply
 

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