LeetCode LCR 039. 柱状图中最大的矩形

Categories:

题目描述
思路分析
1. 解法一：单调栈 + 哨兵（推荐）
相似题目

题目描述

✅ LCR 039. 柱状图中最大的矩形

思路分析

解法一：单调栈 + 哨兵（推荐）

核心思路：

以某根柱子为高度的最大矩形，宽度由左边第一个比它矮的柱子和右边第一个比它矮的柱子决定。

维护一个单调递增栈（存下标），当遇到比栈顶更矮的柱子时，弹出栈顶并以其高度计算面积。

在数组首尾各插入高度为 0 的哨兵，保证所有柱子最终都能被弹出，无需单独处理边界。

弹出栈顶 top 时：右边界是当前下标 i，左边界是新栈顶下标，宽度 = i - newTop - 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示柱子数量，每个元素最多入栈、出栈各一次

空间复杂度：O(n)，单调栈最多存储 n+2 个下标

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 首尾各加一个高度为 0 的哨兵，确保所有柱子都能被弹出
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int maxArea = 0;
        for (int i = 1; i < h.length; i++) {
            // 当前柱子比栈顶矮时，弹出栈顶并计算以其为高的最大矩形
            while (h[i] < h[stack.peek()]) {
                int top = stack.pop();
                // 左边界为新栈顶，右边界为 i，宽度为两者之差减 1
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h[top] * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

func largestRectangleArea(heights []int) int {
    // 首尾各加一个高度为 0 的哨兵，确保所有柱子都能被弹出
    heights = append([]int{0}, append(heights, 0)...)
    stack := []int{0}
    maxArea := 0
    for i := 1; i < len(heights); i++ {
        // 当前柱子比栈顶矮时，弹出栈顶并计算以其为高的最大矩形
        for heights[i] < heights[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 左边界为新栈顶，右边界为 i，宽度为两者之差减 1
            width := i - stack[len(stack)-1] - 1
            area := heights[top] * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

相似题目

题目	难度	考察点
85. 最大矩形	困难	单调栈
42. 接雨水	困难	双指针、单调栈
11. 盛最多水的容器	中等	双指针
739. 每日温度	中等	单调栈
496. 下一个更大元素 I	简单	单调栈
503. 下一个更大元素 II	中等	单调栈
907. 子数组的最小值之和	中等	单调栈
1793. 好子数组的最大分数	困难	单调栈
2104. 子数组范围和	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/87749836