［leetcode］Traping Rain Water

この問題は神様の問題です.最初は私もリンクhttp://www.cnblogs.com/lichen782/p/Leetcode_Traping_Rain_Water.の中を参考にして、久しぶりに「テトリス」の考えを考えました.複雑さが足りないです.
その後方法二を見ましたが、確かに巧妙です.「実は、本质的には、第一歩は左右の水がいつも「中に入れる」ことを保障しています.大きな板は中间に置いてありますから.

public class Solution {

    public int trap(int[] A) {

        // Start typing your Java solution below

        // DO NOT write main() function

        int len = A.length;

        if (len == 0) return 0;

        int maxIndex = 0;

        for (int i = 0; i < len; i++) {

            if (A[i] > A[maxIndex]) {

                maxIndex = i;

            }

        }       

        

        int water = 0;

        int curMax = 0;

        // left to max

        for (int i = 0; i < maxIndex; i++) {

            if (A[i] > curMax) {

                curMax = A[i];

            }

            else if (A[i] < curMax) {

                water += (curMax - A[i]);

            }

        }

        curMax = 0;

        // right to max

        for (int i = len - 1; i > maxIndex; i--) {

            if (A[i] > curMax) {

                curMax = A[i];

            }

            else if (A[i] < curMax) {

                water += (curMax - A[i]);

            }

        }

        

        return water;

    }

}

第二ブラシは単調なスタックで解決しましたが、Annieの方法で、両方の高いところを見つけたほうがいいです.

int trap(int A[], int n) {

        stack<int> stk; // descending

        int result = 0;

        int i = 0;

        while (i < n) {

            if (stk.size() == 0 || A[stk.top()] > A[i]) {

                stk.push(i); // the index

                i++;

            } else { // A[i] >= stk.top();

                int j = stk.top();

                stk.pop();

                if (stk.size() != 0) {

                    result += (i - stk.top() - 1) * (min(A[stk.top()], A[i]) - A[j]);

                }

            }

        }

        return result;

    }

    

    // Solution: Find left bound and right bound for each element. O(n).

    int trap_1(int A[], int n) {

        if (n == 0) return 0;

        vector<int> maxLeft(n,0);

        vector<int> maxRight(n,0);

        maxLeft[0] = A[0];

        maxRight[n - 1] = A[n - 1];

        for (int i = 1; i < n; ++i) {

            maxLeft[i] = max(maxLeft[i - 1], A[i]);

            maxRight[n - 1 - i] = max(maxRight[n - i], A[n - 1 - i]);

        }

        

        int res = 0;

        for (int i = 1; i < n; ++i) {

            res += min(maxLeft[i], maxRight[i]) - A[i];

        }

        return res;

    }