I like the recursive solution to this.


  • -4
    Y

    You can figure out what the recursive solution is.

    :D


  • 0
    E

    Here is my recursive solution.

    class Solution {
    public:
        int trap(int A[], int n) {
            int left = 0, right = n - 1;
            int height = A[left] < A[right] ? A[left] : A[right];
            int max = -1, index = -1;
            for(int i = left + 1; i < right; i++) {
                if(A[i] > max) {
                    max = A[i];
                    index = i;
                }
            }
            if(height < max)
                return trap(A, index + 1) + trap(A + index, right - index + 1);
            int sum = (right - left - 1) * height;
            if(sum <= 0)
                return 0;
            for(int i = left + 1; i < right; i++) {
                sum -= height < A[i] ? height : A[i];
            }
            return sum;
        }
    };

Log in to reply
 

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