本題來自Leetcode，題目傳送門：「鏈接」

難度：困難

編程語言：Go

1. 題目介紹

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

引用自Leetcode

提示：

1. n == height.length

2. 1 <= n <= 

3. 0 <= height[i] <= 

2. 解題思路

要接住雨水，必須形成凹槽。

第一種思路：找到這個柱子左邊最高的，和右邊最高的，然后計算這個柱子能接到的雨水。量=min(左邊最高，右邊最高)。

這種方法下：

1. 每一個柱子都要往兩邊擴散計算，時間復雜度是O(n)

2. 需要兩個額外的數組來保留n個柱子能接到的雨水，空間復雜度為O(n).

第二種思路：尋找比左邊高的柱子。 當找到凹槽后，可累積的雨水為：超過該高度的面積。比如：

    1  ~  ~  ~  1
    1  1  *  1  1
    1  1  1  1  1

從第四個柱子開始，出現第一個凹槽，可累計的雨水是"*"，寬為1，高為1 ，累積雨水1個單位。

第五個柱子出現第二個凹槽，其和等高的柱子（第一個柱子）的寬度"～"為3，高為1，所以累積的雨水是3個單位。

圖示被丟棄的圖樣：

         1
      1  1     2
   1  1  1  1  2

從第一個柱子開始，左低右高，無法形成凹槽，丟棄。第三個柱子不能丟棄，因為后面可能存在"2"構成的柱子。第四個柱子同理需要保留，但是同樣不累積雨水。

這種方法下：

1. 每一個元素需要入一次棧，時間復雜度為O(n)；

2. 需要一個棧來保存柱子的坐標，最壞情況下保留n個，空間復雜度為O(n)；

第三種思路：由于接到的雨水由左右兩個最高的高度的最小值決定，所以可以從左右兩側往中間靠攏，動態的計算左右的最大值。

其中的難點：當從左往右時，左邊的最大值是可信的，但是右邊的最大值 <= 右邊真實的最大值。同理，從右往左也是如此。

這種情況下，如果是從左往右且左邊的最大值小于右邊的最大值，則該柱子接到的雨水必然等于：左邊最大值-當前柱子的高度。同理從右往左，右邊最大值小于左邊最大值時，也是如此。

則這種情況下，按照相同方向靠攏是可靠的，如從左往右的繼續向右計算下一個柱子的累積雨水情況。如果左邊最大值小于右邊最大值，則右邊向左靠攏。

這種方法下：

1. 每一個元素需要一次遍歷，時間復雜度為O(n)；

2. 需要保留leftMax和rightMax,空間復雜度為O(1)。

3. 源碼展示

先上測試

第一種方法比較簡單，此處不實現。

第二種方法：

第三種方法：

Leetcode運算結果

方法二：

• 執行用時: 16 ms
• 內存消耗: 6.7 MB

方法三：

• 執行用時: 4 ms
• 內存消耗: 5.1 MB