题目描述:
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [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 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
解题思路一:单调栈,维护一个单调递减栈。每当遇到当前元素大于栈顶元素就出栈,在出栈时更新答案。当遇到出栈的情况,若单调栈栈左边有一个元素则必有height[left] > height[top],有因为当前元素大于栈顶,那么可以得到当前的接到的雨水量,宽是i - left - 1,长是min(height[i], height[left]) - height[top]。根据宽度和高度即可计算得到该区域能接的雨水量。
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
stack = []
ans = 0
for i, h in enumerate(height):
while stack and h > height[stack[-1]]:
top = stack.pop()
if not stack: break
left = stack[-1]
currWeith = i - left - 1
currHeight = min(height[i], height[left]) - height[top]
ans += currWeith * currHeight
stack.append(i)
return ans
时间复杂度:O(n) 其中 n 是数组 height的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
空间复杂度:O(n) 空间复杂度主要取决于栈空间,栈的大小不会超过 n。
解题思路二:动态规划,其实很简单。我们只需要知道一个结论,遇到当前元素i,这个位置接的雨水量是min(leftMax[i], rightMax[i]) - height[i],即该位置左右两边最大值的小的一个减去当前位置的高度。这样就简单了,我们只需要遍历两遍数组得到左边最大值和右边最大值即可。
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n = len(height)
leftMax = [height[0]] + [0] * (n - 1)
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
rightMax = [0] * (n - 1) + [height[n - 1]]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
return ans
时间复杂度:O(n),其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次,计算能接的雨水总量还需要遍历一次。
空间复杂度:O(n),其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax和 rightMax。
解题思路三:双指针,用双指针代替动态规划的两个数组,这里用leftMax , rightMax维护左右当前最大值,如果左边高度小则,left右移且更新答案;如果右边高度大于等于左边,则right左移且更新答案。
这样是一定能够保证,left += 1的时候一定是左边最大值更小。文章来源:https://www.toymoban.com/news/detail-764465.html
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left, right = 0, len(height) - 1
leftMax = rightMax = 0
while left < right:
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if height[left] < height[right]:
ans += leftMax - height[left]
left += 1
else:
ans += rightMax - height[right]
right -= 1
return ans
时间复杂度:O(n)
空间复杂度:O(1)文章来源地址https://www.toymoban.com/news/detail-764465.html
到了这里,关于LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!