原題

給出 n 個(gè)非負(fù)整數(shù)，代表一張X軸上每個(gè)區(qū)域?qū)挾葹?1 的海拔圖, 計(jì)算這個(gè)海拔圖最多能接住多少（面積）雨水。

海拔分別為 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.

解題思路

• 一塊直柱能接的水取決于左右兩邊較短的高度，所以第一個(gè)比較直觀的方法是從左到有遍歷一遍記錄該點(diǎn)左邊的最大值，從右到左遍歷一遍記錄該點(diǎn)的右邊的最大值，此方法為O(n) 時(shí)間, O(n) 空間，第二種方法可以利用單調(diào)遞減棧來實(shí)現(xiàn)，此方法為O(n) 時(shí)間, O(n) 空間
• 第三種方法為先找出中間最大點(diǎn)，然后左邊部分相當(dāng)于已經(jīng)確定了右邊最大值，左指針不斷向右逼近就行，右邊部分相當(dāng)于記錄了左邊最大值，右指針不斷向左逼近就行，此方法為O(n) 時(shí)間, O(1) 空間，第四種方法類似第三種，左右夾逼，每次選擇小的那個(gè)指針向中間靠攏，此方法為O(n) 時(shí)間, O(1) 空間，但是要比方法三少遍歷一遍。

完整代碼

# 方法三
class Solution:
    # @param heights: a list of integers
    # @return: a integer
    def trapRainWater(self, heights):
        water = 0
        MaxIndex = -1
        MaxHeight = -1
        for i in range(1, len(heights)):
            if heights[i] > MaxHeight:
                MaxHeight = heights[i]
                MaxIndex = i
                
        prev = 0
        for i in range(0, MaxIndex):
            if heights[i] > prev:
                water += (heights[i] - prev) * (MaxIndex - i)
                prev = heights[i]
            water -= heights[i]
            
        prev = 0
        for i in range(len(heights) - 1, MaxIndex, -1):
            if heights[i] > prev:
                water += (heights[i] - prev) * (i - MaxIndex)
                prev = heights[i]
            water -= heights[i]
            
        return water

# 方法四
class Solution:
    # @param heights: a list of integers
    # @return: a integer
    def trapRainWater(self, heights):
        n = len(heights)
        l, r, water, minHeight = 0, n - 1, 0, 0
        while l < r:
            while l < r and heights[l] <= minHeight:
                water += minHeight - heights[l]
                l += 1
            while l < r and heights[r] <= minHeight:
                water += minHeight - heights[r]
                r -= 1
            minHeight = min(heights[l], heights[r])
        return water