LeetCode42接雨水

发布于:2021-07-21 20:53:26

题目描述:

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



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


示例:


输入: [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


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)

相关推荐

最新更新

猜你喜欢