单调栈
解题思路
声明一个单调递减的栈；
遍历柱子，维护这个单调栈，并计算凹槽的面积；
入栈：如果
当前的板子高度 < 栈顶板子高度，则不会形成凹槽，则入栈该板子；出栈：如果
当前的板子高度 > 栈顶板子高度，则会形成凹槽；
- 出栈栈顶板子高度为 top，此时栈顶板子高度为 top‘、索引为 h‘；
- 计算宽度：
当前板子索引 - h‘ - 1；- 计算高度：
Math.min(当前板子高度, top‘) - top；- 面积 = 宽 * 高，根据已知的宽度和高度求出凹槽的面积；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是数组 height 的长度；从 0 到 n−1 的每个下标最多只会入栈和出栈各一次； -
空间复杂度：
O(n)，其中 n 是数组 height 的长度；空间复杂度主要取决于栈空间，栈的大小不会超过 n；
代码实现
var trap = function (height) {
// 1. 声明一个单调递减的栈
let res = 0;
const stack = [];
// 2. 遍历柱子，维护这个单调栈
for (let i = 0; i < height.length; ++i) {
// 2-1. 如果栈不为空，且栈顶元素<当前柱子的高度，说明可以形成水坑
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
const top = stack.pop();
if (!stack.length) break;
const left = stack[stack.length - 1];
const currWidth = i - left - 1;
const currHeight = Math.min(height[left], height[i]) - height[top];
res += currWidth * currHeight;
}
// 2-2. 放入单调栈
stack.push(i);
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 236. 二叉树的最近公共祖先
上一篇
评论
