10lines Java solution. Time=O(n), Space=O(n), (java8 stream)


  • 0
    M
        public int trap(int[] A) {
            int N = A.length;
            int[] L = Arrays.copyOf(A, N);
            int[] R = Arrays.copyOf(A, N);
            for (int i = 1, j = N - 2; i < N; i++, j--) {
                L[i] = Math.max(L[i - 1], A[i]);
                R[j] = Math.max(R[j + 1], A[j]);
            }
            return IntStream.range(0, N).map(i -> Math.min(L[i], R[i]) - A[i]).sum();
        }
    

Log in to reply
 

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