[Leetcode 42] 接雨水

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
notion image
示例 2:
 

解法一:动态规划

预处理两个数组:
  • leftMax[i]:从左到 i 的最高柱;
  • rightMax[i]:从右到 i 的最高柱。
位置 i 的接水量 = min(leftMax[i], rightMax[i]) - height[i](若为负则记 0,代码里天然不会为负)。
复杂度
  • 时间:O(n)(两次线性预处理 + 一次求和)
  • 空间:O(n)(两张表)

解法二:单调栈

单调递减栈存索引。遇到当前高度 h 大于栈顶高度,说明形成“盆地底部”:
  • 弹出底部 top,此时若栈空则无法形成左边界,继续;
  • 否则左边界在 left = stack[-1],宽度 i - left - 1,有效高度 min(height[left], height[i]) - height[top]
    • 把这块水量结算到答案里;最后把当前索引入栈,继续。
复杂度
  • 时间:O(n)(每个索引最多入栈/出栈一次)
  • 空间:O(n)(栈)

解法三:双指针(推荐)

思路:维护左右指针 left/right 与两侧最大值 leftMax/rightMax
  • height[left] < height[right],则左侧短板先决定 left 位置的水量,即 leftMax - height[left];左指针右移。
  • 否则由右侧短板决定 right 位置水量,即 rightMax - height[right];右指针左移。
    • 不断推进直到相遇。
复杂度
  • 时间:O(n)
  • 空间:O(1)
上一篇
[Leetcode 34] 在排序数组中查找元素的第一个和最后一个位置
下一篇
[Leetcode 44] 通配符匹配