单调栈
解题思路
维护一个单调递增栈，
遇到一个元素 < 栈顶元素说明区间在 [栈顶元素索引，当前元素索引] 是矩形的宽度区间，矩形的高度是 heights[i] ，则可以计算出矩形的面积；将 heights 数组前后各加入一个 哨兵元素 0：
- 栈空了，面积公式就没法用了，当栈只有一个元素，栈顶出栈，栈就空了，则无法计算 矩形的宽度 了；
- 最后一个 bar 需要解救，最后一个 bar 不会遇到新 bar 了，如果它在栈中，那就没有机会出栈了，就没有机会计算栈中的长方形面积了；
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(n)
代码实现
const largestRectangleArea = (heights) => {
const stack = [];
let maxArea = 0;
heights = [0, ...heights, 0];
for (let i = 0; i < heights.length; i++) {
// 当前 bar 比栈顶 bar 矮
while (heights[stack[stack.length - 1]] > heights[i]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1));
}
// 当前 bar 比栈顶 bar 高了，入栈
stack.push(i);
}
return maxArea;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 108. 将有序数组转换为二叉搜索树
上一篇
评论
