题目
给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解题思路
具体思路可参考 42. 接雨水
代码
解法一:动态规划
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
leftmax = [0]*n
rightmax = [0]*n
left_max = 0
right_max = 0
res = 0
for i in range(n):
if height[i]>left_max:
left_max = height[i]
leftmax[i] = left_max
if height[n-1-i]>right_max:
right_max = height[n-1-i]
rightmax[n-1-i] = right_max
for i in range(n):
res += min(leftmax[i], rightmax[i]) - height[i]
return res
解法二:双指针
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
leftmax = 0
rightmax = 0
left = 0
right = n-1
res = 0
while left<=right:
if leftmax<rightmax:
leftmax = max(leftmax, height[left])
res += leftmax - height[left]
left += 1
else:
rightmax = max(rightmax, height[right])
res += rightmax - height[right]
right -= 1
return res
解法三:单调栈
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
stack = []
res = 0
for i in range(n):
while stack and height[stack[-1]] < height[i]:
bottomid = stack.pop()
while stack and height[stack[-1]] == height[bottomid]:
stack.pop()
if stack:
h = min(height[stack[-1]], height[i]) - height[bottomid]
w = i - stack[-1] - 1
res += h*w
stack.append(i)
return res