leetcode 42. 接雨水

Posted on | In , ,

题目

42. 接雨水

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

img

上面是由数组 [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
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution:
    '''
        首先这个题目让我想起了之前做过的一些题目的感觉

        好像是股票那个题目。  求得收益

        分析这个题目：首先是要接水。

            思路：
                    事实上要是有两个最高的柱子，就可以支起一个水池子。

                    但是在遍历过程中一般都是走到这山望得那山高这个山柱子担当水柱子，在下一个池子里也可以担当水池子。
                    但是，一旦在后面遇到了一个更高的山可能就把这个山头给淹没了。
                    这里计算得到的结果就没用了。
                        所以用一个列表把这些水柱子的位置都记住。然后计算了盛的水后，可以把它给填了。
                        在后面遇到更高的山时就不会计算两边

            也想到可以用栈来实现：
                如果要入栈的柱子比栈顶高就出栈：
                    如果碰到栈底则直接弹出把当前要入栈的入栈就好了。
                    出栈一次后，如果此时栈顶与之前栈顶相等接着出栈
                    如果（此时栈顶大于之前栈顶）并且（此时栈顶小于等于要入栈的柱子）就在接的雨水值加上 ：
                        （此时栈顶- 之前栈顶）*他们的距离，然后出栈，再把要入栈的入栈
                    如果（此时栈顶大于之前栈顶）并且（此时栈顶大于要入栈的柱子）就在接的雨水值加上 ：
                        （要入栈的柱子-之前栈顶）*他们的距离，然后要入栈的入栈
                    直到可以蓄水也就是比中间的值大一点（入栈是非递增的:增减+持续相等）
                如果比栈顶低或者等于栈底就入栈

    '''


    def trap(self, height):
        # 在栈中保存的是柱子的索引
        stack = []
        res = 0     # 储存的水量
        flag = True # 栈为空表示为真
        for i in range(len(height)):
            if flag:
                stack.append(i)
                flag = False
            elif height[i] <= height[stack[-1]]:
                stack.append(i)
            else:
                while height[i] > height[stack[-1]]:
                    temp = stack[-1]
                    while height[stack[-1]] == height[temp]:
                        print(temp)
                        temp = stack.pop()
                        if not stack:   # 到栈底了  （因为已经出来了一个了，此时也很有可能为空的）
                            # 这时也就是要进来的这个水柱在之前是无法储水的
                            flag = True
                            break

                    # 直到栈顶和之前出栈的不相等时,计算中间能存多少水
                    # 此时有两种情况：
                    #       1. 栈空了
                    #       2. 值更大了。
                    #           a. 此时栈顶小于等于要入栈的柱子
                    #           b. 此时栈顶大于要入栈的柱子
                    if flag:
                        break
                    else:
                        if height[stack[-1]] <= height[i]:
                            res += (i - stack[-1] -1) * (height[stack[-1]] - height[temp])
                        else:
                            res += (i - stack[-1] - 1) * (height[i] - height[temp])
                stack.append(i)
                if flag:
                    flag = False;
        return res
if __name__ == "__main__":
    a = Solution()
    print(a.trap([0,5,6,4,6,1,0,0,2,7]))