LeetCode 42.接雨水

发表于 更新于 分类于

题目地址

https://leetcode-cn.com/problems/trapping-rain-water/

解题

把柱子按高度分成不同组, 从高到低开始取, 每组取完后计算hi hn(下一组的高度)之间存在多少块水, 数量为(maxi - mini + 1 - (i + 1)) * (hi - hn), 其中i从0开始, maxi - mini + 1表示宽度, i+1表示柱子的数量

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
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        ihs = [(i,height[i]) for i in range(len(height))]
        ihs.sort(key = lambda x : x[1], reverse = True)
        ans = 0
        maxi = -1
        mini = -1
        for i in range(len(ihs)):
            idx, h = ihs[i]
            if maxi == -1 or idx>maxi:
                maxi = idx
            if mini == -1 or idx<mini:
                mini = idx
            
            dh = 0
            if i == len(ihs)-1:
                dh = 1
            else:
                dh = h - ihs[i+1][1]
            if dh:
                ans += (maxi - mini - i) * dh
        
        return ans


print(Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]))