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

示例 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)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-42-接雨水
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 34] 在排序数组中查找元素的第一个和最后一个位置
下一篇
[Leetcode 44] 通配符匹配