What is the optimal approach for Largest Rectangle in Histogram?

The optimal solution uses a monotonic stack to track indices of increasing heights, allowing O(n) area computation for each rectangle.

Why is a stack used instead of nested loops?

Nested loops result in O(n^2) time, which is too slow for large arrays. A stack ensures each bar is considered efficiently once.

How do you handle consecutive bars of equal height?

Consecutive bars of equal height are processed by popping from the stack until the top is strictly less, ensuring correct width calculation for maximal rectangles.

What are common mistakes when implementing this problem?

Mistakes include not adding a sentinel zero-height bar, incorrect width calculation when stack empties, or confusing indices with heights.

Can this stack pattern be reused in other histogram problems?

Yes, any problem requiring contiguous maximal area tracking, like skyline or maximal square variations, benefits from this monotonic stack approach.

#84

Hard

auto_awesome栈·状态

LeetCode 题解工作台

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例 1: 输入： heights = [2,1,5,6,2,3] 输出： 10 解释：最大的矩形为图中红色区域，面积为 10 示例 2：输入： height…

数组栈单调栈

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=10⁵
0 <= heights[i] <= 10⁴

lightbulb

解题思路

方法一：单调栈

我们可以枚举每根柱子的高度 $h$ 作为矩形的高度，利用单调栈，向左右两边找第一个高度小于 $h$ 的下标 $left_i$ , $right_i$ 。那么此时矩形面积为 $h \times (right_i-left_i-1)$ ，求最大值即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 表示 $heights$ 的长度。

单调栈常见模型：找出每个数左/右边离它最近的且比它大/小的数。模板：

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stk = []
        left = [-1] * n
        right = [n] * n
        for i, h in enumerate(heights):
            while stk and heights[stk[-1]] >= h:
                right[stk[-1]] = i
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

speed

复杂度分析

指标	值
时间	complexity is O(n) because each bar is pushed and popped at most once from the stack. Space complexity is O(n) for storing indices in the stack during the monotonic traversal.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
You might be prompted to explain why a naive O(n^2) approach fails for large histograms.
question_mark
Clarify how stack state ensures all rectangle widths are computed correctly without missing any bar combinations.
question_mark
Expect questions on handling equal-height bars and ensuring correct width computation for consecutive duplicates.

warning

常见陷阱

外企场景

error
Forgetting to add a sentinel zero-height bar to process remaining stack elements.
error
Incorrect width calculation when the stack becomes empty after popping.
error
Pushing indices instead of heights can lead to miscalculating rectangle areas.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Largest rectangle under skyline silhouette problems, where heights may vary non-uniformly and require similar stack techniques.
arrow_right_alt
Finding maximal square instead of rectangle in a histogram-like 2D matrix using modified state management.
arrow_right_alt
Calculating largest rectangle in a histogram with additional constraints on minimum or maximum allowed heights.

help

常见问题

外企场景

继续练习

#85 最大矩形 #42 接雨水 #321 拼接最大数