⚡Flashcard Drill➔
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

  1. For each bar, the largest rectangle using that bar as the limiting height extends left and right until a shorter bar is found.
  2. A monotonically increasing stack of indices identifies those boundaries efficiently.
  3. 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.
  4. 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 is i - 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems