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

柱状图中最大的矩形

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

题型判断

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

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

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

这样宽度就是：

right - left - 1

核心思路

维护一个按高度非递减的栈，栈里放下标；本实现保留等高柱。

当当前柱子更矮时：

• 说明栈顶柱子的右边第一个更小元素找到了
• 弹出栈顶 mid
• 新的栈顶是本次结算的左边界，可能与 mid 等高
• 立刻计算以 mid 为高的面积

例如 [2, 2] 遇到末尾 0，右侧的 2 先结算宽度 1，左侧的 2 再结算宽度 2。不是每个柱子都拿到了两侧严格更小边界，但最大面积不会遗漏。

为什么常常前后补 0

• 前面的 0：统一左边界
• 后面的 0：结算剩余的正高度柱；高度为 0 的柱可能留栈，但面积为 0

这里依赖题目柱高非负、每根柱宽为 1。前置 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;
};

一句话总结

弹栈时按当前结算边界计算面积，等高柱的更宽范围由后续弹栈覆盖。总时间 O(n)，栈和复制后的高度数组使用 O(n) 额外空间。