21 ms Java solution O(n)


  • 0
    A
    public class Solution {
        public int trap(int[] input) {
            if (input.length == 0) return 0;
            int[] leftLargest = new int[input.length];
            int[] rightLargest = new int[input.length];
            int max = 0;
            for (int i = 1; i <= input.length - 1; i++) {
                max = Math.max(max, input[i - 1]);
                leftLargest[i] = max;
            }
            max = 0;
            for (int i = input.length - 2; i >= 0; i--) {
                max = Math.max(max, input[i + 1]);
                rightLargest[i] = max;
            }
            int result = 0;
            for (int i = 1; i <= input.length - 2; i++) {
                int maxBoundaryHeight = Math.min(leftLargest[i], rightLargest[i]);
                if (maxBoundaryHeight > input[i]) result += maxBoundaryHeight - input[i];
                //System.out.println(result);
            }
            return result;
        }
    }
    

Log in to reply
 

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