LeetCode解題之Trapping Rain Water

原題

計算一個凹凸不平的模型中可以存放多少的雨水。以下圖為例，黑色的地方是磚塊，藍色的地方是積水。

注意點：<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCrj4tcSyzsr9yv3X6bHtyr61xMrH16m/6bXEuN+2yKOoy/zX1Mnt0rLSqtW8w+a7/aOpo6yyu9a7ysex3yCyu7vhtObU2ri6yv21xMfpv/YNCjxwPsD919OjujwvcD4NCjxwPsrkyOs6IGhlaWdodCA9IFswLDEsMCwyLDEsMCwxLDMsMiwxLDIsMV08YnIgLz4NCsrks/Y6IDY8L3A+DQo8YmxvY2txdW90ZT4NCgk8cD7XoqO6vt/M5b+0yc/NvDwvcD4NCjwvYmxvY2txdW90ZT4NCjxoMiBpZD0="解題思路">解題思路

這題與 Container With Most Water 非常相似，但那題只需要求出面積最大的積水處，而現在要找到所有的積水處的總和。現在考慮任意的一個塊磚它上面最終的積水高度是如何求的，我們需要找到它左右兩邊的最高的磚塊，而它最終的高度就是這兩個磚塊中較矮的那個。所有我們需要先遍歷來得到每個磚塊左右最高磚塊的高度，最後根據這兩個高度來確定最終的高度。下面的代碼先從後往前遍歷得到右邊的最高高度，然後從前往後遍歷得到左邊的最高高度，同時得到兩者中小的一個加入總和。

AC源碼

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        length = len(height)
        maxh = [0 for __ in range(length)]
        h = height[length - 1]
        for i in range(length - 2, -1, -1):
            maxh[i] = h
            h = max(h, height[i])

        h = height[0]
        result = 0
        for i in range(1, length - 1):
            h = max(h, height[i])
            result += max(0, min(h, maxh[i]) - height[i])
        return result


if __name__ == "__main__":
    assert Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6

歡迎查看我的Python">Github來獲得相關源碼。