LeetCode 42 Trapping Rain Water

Description

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.

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!

Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6.

描述

給定n個(gè)非負(fù)整數(shù)，每個(gè)非負(fù)整數(shù)表示一個(gè)寬度為1的柱子，計(jì)算下雨后能夠捕獲多少水.

rainwatertrap

上面的柱狀圖由數(shù)組[0,1,0,2,1,0,1,3,2,1,2,1]表示。在這種情況下，藍(lán)色部分表示的6個(gè)單位雨水可以被柱子圍住.

例: 輸入: [0,1,0,2,1,0,1,3,2,1,2,1] 輸出: 6.

思路一

• 我們觀察圖中所示的例子，一每一個(gè)柱子為思考點(diǎn)，想一下它能夠裝的水是由什么決定的呢？
• 以編號(hào)為5的柱子(令示例中的數(shù)組為a，即a[5]=0)為例，觀察發(fā)現(xiàn)：
• 每個(gè)柱子能夠困住的水是由以柱子所在位置為基點(diǎn)，此基點(diǎn)左邊所有柱子中最大值和此基點(diǎn)右邊所有柱子中最大值共同決定的，即：
• A[5]能困住的水 = Min{A[5]左邊所有柱子的最大值，A[5]右邊所有柱子的最大值} - A[5].

有了這個(gè)思路，就有了第一種解決方案：

• 從左往右遍歷數(shù)組，找到每一個(gè)值左邊的最大值，用一個(gè)數(shù)組記錄下來
• 從右往左遍歷數(shù)組，找到每一個(gè)值右邊的最大值，用一個(gè)數(shù)組記錄下來
• 能夠裝的水=min(該位置左邊最大值，該位置右邊最大值)-該位置的值
• 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 數(shù)組的長(zhǎng)度，如果數(shù)組長(zhǎng)度小于等于2，則一定裝不了水
        length = len(height)
        if length <= 2:
            return 0
        # 聲明兩個(gè)數(shù)組，分別用于存儲(chǔ)左邊的最大值和右邊的最大值
        leftmax, rightmax = [0]*length, [0]*length
        temp, water = 0, 0
        # 找到左邊的最大值
        for index in range(length):
            if height[index] >= temp:
                temp = height[index]
            leftmax[index] = temp
        # 找到右邊的最大值
        temp = 0
        for index in range(length-1, -1, -1):
            if height[index] >= temp:
                temp = height[index]
            rightmax[index] = temp
        # 遍歷求和
        for index in range(length):
            water += min(leftmax[index], rightmax[index])-height[index]
        return water

思路二

• 在思路一中，我們從每一個(gè)柱子出發(fā)，思考到?jīng)Q定每個(gè)柱子能容多少水是由該柱子左邊最高的柱子和該柱子右邊最高的柱子共同決定的，
• 因此我們?yōu)槊恳粋€(gè)柱子求得其左邊最高的柱子和右邊最高的柱子，這樣空間復(fù)雜度是O(n)。但是我們反過來想，其實(shí)有很多柱子的左右最高柱.
• 是一樣的，也就是說有很多柱子左右最高柱子使用同一對(duì)柱作為最高柱.于是，我們可以反過來，看在左右最高柱確定的情況下，哪些柱子以這兩個(gè)柱為最高柱.
• 我們需要四個(gè)值，leftmax:左邊最高柱子的值,left:當(dāng)前左邊柱子的索引，rightmax：右邊最高柱子的值，right:當(dāng)前右邊柱子的值.畫圖最直觀.

20181203leetcode42-001.png

• 如上圖1，左邊的最高值leftmax和右邊的最高值rightmax已經(jīng)確定，索引為left和right的柱子之間還有柱子.
• 如果leftmax<=rightmax,索引為left的柱子能夠裝的水就確定了，為leftmax-left柱子自身的高度，而索引為right的柱子還不確定.
• 因?yàn)閘eft和right中間無論有什么情況的柱子:如果有比left高的柱子，left裝水量由左邊矮的leftmax確定，為leftmax-自身高度.
• 如果有比left矮的柱子,但是由于rightmax比較大，left也可以達(dá)到leftmax的高度.
• 但是right并不能確定,如果left和right有更高的柱子，right就可以裝水，如果沒有，right就無法裝水.
• 反過來，如果leftmax>rightmax,則right就能確定,而left不能確定.如下圖2.

20181203leetcode42-002.png

有了這個(gè)思路就有了第二個(gè)解決方案

• 更新左邊柱子的最大值leftmax.
• 更新右邊柱子的最大值rightmax.
• 如果leftmax<=rightmax,則該柱子出水量為leftmax-自身高度,left向右走一步.
• 如果leftmax>rightmax,則該柱子出水量為rightmax-自身高度,rihgh向左走一步.
• 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 數(shù)組的長(zhǎng)度，如果數(shù)組長(zhǎng)度小于等于2，則一定裝不了水
        length = len(height)
        if length <= 2:
            return 0
        # 聲明五個(gè)變量，總水量，左邊最高柱的值，右邊最高柱的值，左邊柱子的索引，右邊柱子的索引
        water, leftmax, rightmax, left, right = 0, 0, 0, 0, length-1
        # 只有左邊索引小于右邊索引才執(zhí)行
        while left < right:
            # 更新左邊最高柱子
            if height[left] > leftmax:
                leftmax = height[left]
            # 更新右邊最高柱子
            if height[right] > rightmax:
                rightmax = height[right]
            # 如果是左低右高(包括左右一樣高)的情形
            if leftmax <= rightmax:
                water += leftmax-height[left]
                left += 1
            # 如果是左高右低這種情況
            elif rightmax < leftmax:
                water += rightmax-height[right]
                right -= 1
        return water

優(yōu)化空間

• 在思路二實(shí)現(xiàn)的代碼中，前面兩個(gè)if條件每次都會(huì)判斷，實(shí)際上，如果第一個(gè)條件滿足那么第二個(gè)條件就一定不會(huì)滿足.
• 同樣的道理，如果第二個(gè)條件滿足，那么第一個(gè)條件就不會(huì)滿足，因此，我們可以把代碼改寫成下面的形式.

class Solution3:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 數(shù)組的長(zhǎng)度，如果數(shù)組長(zhǎng)度小于等于2，則一定裝不了水
        length = len(height)
        if length <= 2:
            return 0
        # 聲明五個(gè)變量，總水量，左邊最高柱的值，右邊最高柱的值，左邊柱子的索引，右邊柱子的索引
        water, leftmax, rightmax, left, right = 0, 0, 0, 0, length-1
        # 只有左邊索引小于右邊索引才執(zhí)行
        while left < right:
            # 首先判斷是什么情形,如果是左低右高這種情形
            # 這里隱藏了一點(diǎn)是當(dāng)height[left] <= height[right]時(shí)，leftmax一定小于等于 height[right]
            if height[left] <= height[right]:
                if leftmax > height[left]:
                    water += leftmax-height[left]
                else:
                    leftmax = height[left]
                left += 1
            # 同理，當(dāng)height[left]>height[right]時(shí)，rightmax一定小于等于height[left]
            if height[left] > height[right]:
                if rightmax > height[right]:
                    water += rightmax-height[right]
                else:
                    rightmax = height[right]
                right -= 1
        return water

源代碼文件戳此

?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源，作者信息和本聲明.