A-027● Day 272026.06.02hardleetcode #84neetcode150

Largest Rectangle in Histogram

#array#stack#monotonic-stack

↗ leetcode #84 · largest-rectangle-in-histogram

Problem

· problem

P.027

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

constraints

· 1 ≤ heights.length ≤ 10^5
· 0 ≤ heights[i] ≤ 10^4

// paraphrased summary — see source for full text

examples

example 1input → output

[2,1,5,6,2,3]

example 2input → output

[2,4]

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
What is the width of each bar in the histogram?
☐
Can a rectangle span non-consecutive bars (skipping shorter bars)?
☐
What determines the height of a rectangle?
☐
In example [2,1,5,6,2,3], why is the maximum area 10, not 12?
☐
If all bars have height 0, what is the maximum area?
☐
Can the optimal rectangle consist of just a single bar?
☐
Is the input array always sorted?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Initialize stack

○

stack = []  # pair: (index, height)

○

stack = None

○

stack = [heights[0]]

step 2· Iterate through each bar

○

for i, h in enumerate(heights):

○

for h in heights:

○

for i in range(len(heights)):

step 3· Pop condition: while top is taller│ nested

○

while stack and stack[-1][1] > h:

○

if stack and stack[-1][1] > h:

○

while stack and stack[-1][1] >= h:

step 4· Calculate area for popped bar│ │ nested

○

maxArea = max(maxArea, height * (i - index))

○

maxArea = max(maxArea, height * (i - index - 1))

○

maxArea = max(maxArea, height * i)

step 5· Update start position│ │ nested

○

start = index

○

start = i - 1

○

start = 0

step 6· Push current bar│ nested

○

stack.append((start, h))

○

stack.append((i, h))

○

stack.insert(0, (start, h))

step 7· Process remaining bars in stack

○

for i, h in stack:

○

for _ in stack:

○

for h, i in stack:

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

class Solution:

    def largestRectangleArea(self, heights: List[int]) -> int:

        maxArea = 0

        stack = []  # pair: (index, height)

        for i, h in enumerate(heights):

            start = i

            while stack and stack[-1][1] > h:

                index, height = stack.pop()

                maxArea = max(maxArea, height * (i - index))

                start = index

            stack.append((start, h))

        for i, h in stack:

            maxArea = max(maxArea, h * (len(heights) - i))

        return maxArea

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[2,1,5,6,2,3]

→

case 2

[2,4]

→

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.