[!info] related notes 算法面试题型 MOC 栈 单调栈

柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/

题型判断

这是单调栈最经典的边界题。

对于每个柱子 i，如果把它当成矩形高度，就要找：

• 左边第一个比它小的位置
• 右边第一个比它小的位置

这样宽度就是：

right - left - 1

核心思路

维护一个按高度单调递增的栈，栈里放下标。

当当前柱子更矮时：

• 说明栈顶柱子的右边第一个更小元素找到了
• 弹出栈顶 mid
• 新的栈顶就是它左边第一个更小元素
• 立刻计算以 mid 为高的面积

为什么常常前后补 0

• 前面的 0：统一左边界
• 后面的 0：强制把栈里剩余柱子全部结算掉

这样代码更整齐。

JavaScript

var largestRectangleArea = function(heights) {
    const nums = [0, ...heights, 0];
    const stack = [];
    let ans = 0;

    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[i] < nums[stack[stack.length - 1]]) {
            const mid = stack.pop();
            const left = stack[stack.length - 1];
            const right = i;
            ans = Math.max(ans, nums[mid] * (right - left - 1));
        }
        stack.push(i);
    }

    return ans;
};

一句话总结

弹栈的那一刻，栈顶柱子的左右边界同时被确定，所以面积也就能立刻算出来。