A two-pass O(n) solution inspired by one solution of [Candy]


  • 2
    J

    You'd better solve the Candy puzzle first.

    class Solution {
    public:
        int trap(int A[], int n) {
            vector<int> v(n);
            for (int i = 0; i < n; i++) v[i] = A[i];
            int result = 0;
            for (int l = 0, r = 1; r < n; r++) {
                if (v[l] < 0) {
                    l++;
                    continue;
                }
                if (v[l] <= v[r]) {
                    for (int i = l + 1; i < r; i++) {
                        result += v[l] - v[i];
                        v[i] = v[l];
                    }
                    l = r;
                }
            }
            for (int l = n - 2, r = n - 1; l >= 0; l--) {
                if (v[r] < 0) {
                    r--;
                    continue;
                }
                if (v[l] >= v[r]) {
                    for (int i = r - 1; i > l; i--) {
                        result += v[r] - v[i];
                        v[i] = v[r];
                    }
                    r = l;
                }
            }
            return result;
        }
    };
    
    1. Loop from left to right, if A[left] > 0 and A[right] >= A[left], add water to the container until A[i] == A[left], then find the next container starting after A[right].
    2. Loop from right to left, if A[right] > 0 and A[left] >= A[right], add water to the container until A[i] == A[right], then find the next container starting before A[left].
    3. Return the volume of the total water.

    Demo:

    |      #           |      #           |      #           |      #           |
    |#    ##      #    |#~~~~##      #    |#~~~~##      #    |#~~~~##~~~~~~#    |
    |#   ### #    #    |#~~~### #    #    |#~~~### #    #    |#~~~###~#~~~~#    |
    |#  #### # #  # #  |#~~#### # #  # #  |#~~#### # #  #~#  |#~~####~#~#~~#~#  |
    |# ##### # #### ###|#~##### # #### ###|#~##### # ####~###|#~#####~#~####~###|
    |401234503021140211|401234503021140211|401234503021140211|401234503021140211|

  • 0
    D

    Helps a lot, thanks!


Log in to reply
 

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