NeetCode #378LC-84HardStackNC 150NC 250
← Back to All Problems#378 · #84 · Largest Rectangle in Histogram(柱状图中最大的矩形)
📌 Problem Statement & Constraints
Given an array
heights representing the heights of bars of width 1 in a histogram, return the area of the largest rectangle that fits inside the histogram. Constraints: 1 <= heights.length <= 10^5, 0 <= heights[i] <= 10^4.💡 Core Algorithmic Approaches
- For each bar, the largest rectangle using that bar as the limiting height extends left and right until a shorter bar is found.
- A monotonically increasing stack of indices identifies those boundaries efficiently.
- When a bar shorter than the stack top arrives, the top's rectangle is complete: its height is the popped bar's height and its width is the distance to the previous stack element.
- Appending a sentinel height of 0 at the end forces all remaining bars to be resolved.
💻 Benchmark Python3 Implementation
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = heights + [0] # sentinel flushes the stack
st = [] # indices with increasing heights
best = 0
for i, h in enumerate(heights):
while st and heights[st[-1]] >= h:
height = heights[st.pop()] # this bar's rectangle is complete
# width: from the previous smaller bar (exclusive) to i (exclusive)
width = i if not st else i - st[-1] - 1
best = max(best, height * width)
st.append(i)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack (plus the sentinel copy).
⚠️ Interview Pitfalls & Follow-ups
- Omitting the sentinel: bars left on the stack at the end would never be evaluated.
- Computing the width as
i - j: the correct width excludes the previous smaller bar, so it isi - st[-1] - 1. - Using
>instead of>=in the pop condition: with equal heights either works, but>=keeps the stack strictly increasing and avoids redundant work. - Trying a two-pointer expansion per bar: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.