LeetCode[Array]: Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. 

For example, 

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

這個題目我首先參考了這個Discuss的解法：https://oj.leetcode.com/discuss/18022/sharing-my-java-code-o-n-time-o-1-space

這個解法的思路如下：設定兩個疊代器，一個從最左邊開始，另外一個從最右邊開始，首先去掉兩邊不可能蓄水的堤壩（以題目中的例子為例，最右側的那個堤壩是不可能蓄水的）；然後隻要兩個疊代器未相遇便進行如下循環：首先判斷兩側堤壩的高度，從較低側的堤壩往中間周遊，當發現堤壩高度小于或者等于這個較低高度時則将這個高度差加到蓄水和，否則進行下一次循環。至于為什麼從較低側堤壩周遊，我想這個比較容易想明白，因為較高側并不能保證能夠蓄水。

我在實作的時候，覺得沒有必要進行第一步，即首先去掉兩邊不可能蓄水的堤壩，因為後面的循環依然可以去掉這些不能蓄水的堤壩。

我的C++代碼實作如下：

int trap(int A[], int n) {
        int water = ;
        for (int left = , right = n - ; left < right; )
        {
            int leftHeight  = A[left ];
            int rightHeight = A[right];

            if (leftHeight < rightHeight)
                while (left < right && A[++left ] <= leftHeight ) water += (leftHeight  - A[left ]);
            else
                while (left < right && A[--right] <= rightHeight) water += (rightHeight - A[right]);
        }
        return water;
    }
           

我們從算法的過程中知道：雖然用了二層循環，但是實際上這是個One Pass算法；另外，我們知道要盡量用一層循環代替二層循環（http://blog.csdn.net/chfe007/article/details/25544421）；由于這是個One Pass算法，是以改為一層循環完全是可行的，隻需要增加左右兩個基準高度即可，我的C++代碼實作如下：

int trap(int A[], int n) {
        int water = ;
        int leftStdHeight = , rightStdHeight = ;
        for (int left = , right = n - ; left < right; ) {
            if (A[left] <= A[right]) { A[left ] < leftStdHeight  ? (water += leftStdHeight  - A[left ]) : (leftStdHeight  = A[left ]); ++left ; }
            else                     { A[right] < rightStdHeight ? (water += rightStdHeight - A[right]) : (rightStdHeight = A[right]); --right; }
        }
        return water;
    }
           

以上兩種算法的時間複雜度都是O(N)，空間複雜度都是O(1)，時間性能表現，前者為11ms，後者為13ms，如下圖所示：

另外，這個Discuss：https://oj.leetcode.com/discuss/3546/any-one-pass-solutions提出了一種用總面積減去堤壩本身占據的面積來完成的計算的算法，也可以借鑒一下。