26. 단조 스택 (Monotonic Stack) — 다음 크거나 작은 원소 O(n) 탐색

핵심 인사이트 (3줄 요약)

1. 본질: 단조 스택(Monotonic Stack)은 스택 내 원소가 단조 증가(Monotonically Increasing) 또는 단조 감소(Monotonically Decreasing) 순서를 유지하는 특수 스택 패턴으로, 배열에서 각 원소의 "다음으로 더 큰 원소(Next Greater Element)" 또는 "다음으로 더 작은 원소"를 O(n)에 찾는 데 특화되어 있다.
2. 가치: 단순 이중 루프로 각 원소의 NGE(Next Greater Element)를 구하면 O(n²)이지만, 단조 스택은 각 원소가 스택에 한 번 삽입·한 번 제거되어 전체 O(n)을 보장한다. 히스토그램 최대 직사각형(LeetCode 84), 빗물 트래핑(LeetCode 42), 주식 가격 스팬(LeetCode 901) 등 경쟁 프로그래밍의 클래식 문제들이 이 패턴으로 해결된다.
3. 판단 포인트: 문제에서 "각 원소에 대해 다음/이전의 더 크거나 작은 원소 찾기"를 요구하면 즉시 단조 스택 패턴을 떠올려야 한다. 단조 증가 스택은 다음 더 큰 원소 찾기에, 단조 감소 스택은 다음 더 작은 원소 찾기에 사용한다.

Ⅰ. 개요 및 필요성

문제: 배열 [2, 1, 5, 6, 2, 3]에서 각 원소의 NGE(다음 더 큰 원소)

O(n²) 순진한 접근:
for i in range(n):
    for j in range(i+1, n):  ← 이중 루프 O(n²)
        if arr[j] > arr[i]: ...

단조 스택 O(n):
각 원소를 한 번씩만 처리 → 전체 O(n)

• 📢 섹션 요약 비유: 단조 스택은 콘서트 입장 대기 줄에서 자신보다 키 큰 사람을 앞에 세우는 규칙이다. 키 작은 사람들을 밀어내면서(Pop) 이미 기다리던 사람들의 "다음으로 키 큰 사람"이 누군지 O(1)에 결정된다.

Ⅱ. 아키텍처 및 핵심 원리

NGE (Next Greater Element) 구현

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n  # 기본값: NGE 없음
    stack = []         # 단조 감소 스택 (인덱스 저장)

    for i in range(n):
        # 현재 원소 > 스택 톱 원소이면: 스택 톱의 NGE 결정
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]  # arr[i]가 arr[idx]의 NGE
        stack.append(i)

    return result

# arr = [2, 1, 5, 6, 2, 3]
# NGE:  [5, 5, 6,-1, 3,-1]

시뮬레이션

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

i=0: 스택=[0(val=2)]
i=1: 1<2, 스택=[0,1]
i=2: 5>1→result[1]=5, 5>2→result[0]=5, 스택=[2]
i=3: 6>5→result[2]=6, 스택=[3]
i=4: 2<6, 스택=[3,4]
i=5: 3>2→result[4]=3, 3<6, 스택=[3,5]
끝: 스택에 남은 [3,5] → result = -1

결과: [5, 5, 6, -1, 3, -1]

• 📢 섹션 요약 비유: 단조 스택은 극장의 좌석 배치다. 뒤에서 더 키 큰 사람이 오면 앞의 키 작은 사람들이 차례로 "내 뒤에 더 큰 사람이 왔다"는 것을 알고(NGE 결정) 자리를 비운다.

Ⅲ. 비교 및 연결

• 📢 섹션 요약 비유: 단조 스택 vs 이중 루프는 색인(인덱스)이 있는 책 vs 처음부터 읽는 책이다. 색인(단조 스택)은 원하는 정보를 O(1)에 찾고, 처음부터 읽기(이중 루프)는 O(n)마다 탐색한다.

Ⅳ. 실무 적용 및 기술사 판단

히스토그램 최대 직사각형 (LeetCode 84)

def largest_rectangle(heights):
    stack = []  # 단조 증가 스택
    max_area = 0

    for i, h in enumerate(heights + [0]):  # 마지막에 0 추가
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area
# heights = [2,1,5,6,2,3] → 10

단조 스택 패턴 인식 체크리스트

• "다음으로 더 큰/작은 원소" → 단조 스택

• "이전으로 더 큰/작은 원소" → 역방향 단조 스택

• "범위 내 최솟값/최댓값" → 단조 덱(Monotonic Deque)

• "히스토그램, 빗물, 온도" 유형 → 단조 스택 99%

• 📢 섹션 요약 비유: 단조 스택 패턴 인식은 요리 레시피 패턴 인식이다. 재료 목록(문제 조건)을 보면 어떤 레시피(알고리즘)인지 즉시 판단하는 숙련된 요리사처럼, 문제 유형만 보면 단조 스택을 적용해야 한다는 것을 즉시 알 수 있어야 한다.

Ⅴ. 기대효과 및 결론

단조 스택 패턴은 슬라이딩 윈도우 최솟값/최댓값을 O(n)에 구하는 단조 덱(Monotonic Deque)으로 확장되어, 동적 프로그래밍의 슬라이딩 윈도우 DP 최적화에도 활용된다.

• 📢 섹션 요약 비유: 단조 스택의 핵심은 "이미 필요 없는 것을 과감히 버리는(Pop) 용기"다. 미래에 영향을 줄 수 없는 원소를 스택에서 제거하여 탐색 범위를 극적으로 줄이는 것이 O(n) 달성의 비결이다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[이중 루프 O(n²) — NGE 순진한 탐색]
    │
    ▼
[단조 스택 O(n) — 단조 순서 유지로 최적화]
    │
    ▼
[히스토그램/빗물 응용 — 2D 문제 적용]
    │
    ▼
[단조 덱 — 슬라이딩 윈도우 범위 최솟값/최댓값]
    │
    ▼
[DP 슬라이딩 윈도우 최적화 — O(n²) DP를 O(n)으로]

👶 어린이를 위한 3줄 비유 설명

1. 단조 스택은 줄 서기 게임이에요! 뒤에서 더 큰 수가 오면 앞에 있는 작은 수들이 "내 NGE(다음 더 큰 수)는 이것"이라고 알아채고 줄에서 나와요.
2. 이렇게 하면 모든 수를 딱 한 번씩만 줄에 넣었다 빼기 때문에(O(n)), 이중 루프(O(n²))보다 훨씬 빠르게 답을 구할 수 있어요.
3. 히스토그램 최대 직사각형, 빗물 채우기 같은 어려운 문제들이 모두 이 원리로 해결된답니다!