LeetCode42接雨水

发表于 | 更新于 | 分类于 |
接雨水Python实现

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路：

方法1：

求能接雨水的量，其实可以看做是求“接满”雨水之后图形的面积，减掉原格子的面积的差。

求接满雨水的面积，可以分层求解。类似于木桶效应，求最短木板所能围成的面积。

每一层的面积 = 层高 * （最右大于短板的index - 最左大于短板的index + 1）

最后，将所有层的面积加和并减掉原格子的面积，即为所能接的雨水量。

方法2：

使用堆栈来解决这个问题。

先将第一个柱子压入栈中

之后在压栈的过程中，需要比较当前柱子与栈内最底处的柱子的高度

当当前柱子高度大于或者等于栈底柱子高度时，站内柱子依次出站，并累积计算其与栈底柱子高度差，直到栈底柱子出栈。

此时栈为空，则将当前柱子压入栈。

当达到最后一个柱子时，需比较最后柱子与栈底柱子高度，此时出栈计算高度差时，使用上一步中较低的柱子来比较。计算得到最后的累积和，算法结束。

代码实现：

使用Python3代码实现方法1，如下，GitHub地址为：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c42.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def findLeft(height, h):
    """
    :param height:
    :param h:
    :return: first left index
    """
    for index, item in enumerate(height):
        if item >= h:
            return index


def findRight(height, h):
    """
    :param height:
    :param h:
    :return: first right index
    """
    i = len(height) - 1
    while i >= 0:
        if height[i] >= h:
            return i
        i = i - 1

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        sortHeight = sorted(height)

        if len(height) == 1:
            return 0
        
        pre = 0
        next = 0
        result = 0
        for h in sortHeight:
            if h == next:
                continue
            elif h > next:
                pre = next
                next = h
                left = findLeft(height, next)
                right = findRight(height, next)
                result = result + (next - pre) * (right - left + 1)

        return result - sum(height)