← 전체 회차
A-027● Day 272026.06.02hardleetcode #84neetcode150

히스토그램에서 가장 큰 직사각형

#array#stack#monotonic-stack
↗ leetcode #84 · largest-rectangle-in-histogram
01

문제

· problem
P.027

히스토그램에서 가장 큰 직사각형

↗ leetcode #84

정수 배열 heights가 주어지며, 각 원소는 너비가 1인 히스토그램의 막대 높이를 나타냅니다. 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 반환하세요.

제약
  • · 1 ≤ heights.length ≤ 10^5
  • · 0 ≤ heights[i] ≤ 10^4
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[2,1,5,6,2,3]
10
example 2input → output
[2,4]
4
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    히스토그램에서 각 막대의 너비는 얼마입니까?
  • ☐
    직사각형이 연속되지 않은 막대들을 건너뛰고 포함할 수 있습니까?
  • ☐
    직사각형의 높이는 어떻게 결정됩니까?
  • ☐
    예제 [2,1,5,6,2,3]에서 최대 넓이가 12가 아니라 10인 이유는?
  • ☐
    모든 막대의 높이가 0이면 최대 넓이는?
  • ☐
    최적의 직사각형은 단 하나의 막대로만 구성될 수 있습니까?
  • ☐
    정렬된 배열이 입력될까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 스택 초기화
○
stack = []  # pair: (index, height)
○
stack = None
○
stack = [heights[0]]
step 2· 모든 막대를 순회
○
for i, h in enumerate(heights):
○
for h in heights:
○
for i in range(len(heights)):
step 3· 스택의 상단이 현재 막대보다 높은지 확인│ 중첩
○
while stack and stack[-1][1] > h:
○
if stack and stack[-1][1] > h:
○
while stack and stack[-1][1] >= h:
step 4· 꺼낸 막대의 넓이 계산│ │ 중첩
○
maxArea = max(maxArea, height * (i - index))
○
maxArea = max(maxArea, height * (i - index - 1))
○
maxArea = max(maxArea, height * i)
step 5· 시작 위치 갱신│ │ 중첩
○
start = index
○
start = i - 1
○
start = 0
step 6· 현재 막대를 스택에 추가│ 중첩
○
stack.append((start, h))
○
stack.append((i, h))
○
stack.insert(0, (start, h))
step 7· 남은 막대들 처리
○
for i, h in stack:
○
for _ in stack:
○
for h, i in stack:
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def largestRectangleArea(self, heights: List[int]) -> int:
3
        maxArea = 0
4
        stack = []  # pair: (index, height)
5
6
        for i, h in enumerate(heights):
7
            start = i
8
            while stack and stack[-1][1] > h:
9
                index, height = stack.pop()
10
                maxArea = max(maxArea, height * (i - index))
11
                start = index
12
            stack.append((start, h))
13
14
        for i, h in stack:
15
            maxArea = max(maxArea, h * (len(heights) - i))
16
        return maxArea
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[2,1,5,6,2,3]
→
10
case 2
[2,4]
→
4
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.