DSA Interview Prep · 강의

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

단조 스택으로 왼쪽 경계를 추적하고 한 번의 순회로 히스토그램 안에 들어가는 직사각형의 최대 넓이를 계산합니다.

히스토그램에서 가장 큰 직사각형은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

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

히스토그램에서 가장 큰 직사각형 문제(LeetCode 84)는 막대의 높이를 나타내는 음이 아닌 정수 배열을 제공합니다. 각 막대의 너비는 1입니다. 히스토그램 안에서 만들 수 있는 가장 큰 직사각형의 넓이를 구해야 합니다. 직사각형은 서로 이어진 막대들을 포함해야 하며, 높이는 포함된 막대 중 가장 짧은 막대에 의해 제한됩니다.

완전 탐색 방법은 모든 쌍 (i, j)에 대해 [i, j] 구간의 최소 높이를 구한 뒤 (j - i + 1)을 곱하는 것입니다. 이는 O(n³)이며, 미리 최소값을 계산해도 O(n²)이므로 너무 느립니다. 단조 스택 해법은 O(n)에 실행됩니다.

# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')

# Brute force for small inputs:
def brute_force(heights):
    n = len(heights)
    max_area = 0
    for i in range(n):
        min_h = heights[i]
        for j in range(i, n):
            min_h = min(min_h, heights[j])
            max_area = max(max_area, min_h * (j - i + 1))
    return max_area

print('Brute force answer:', brute_force(heights))  # 10

핵심 통찰: 각 막대의 직사각형을 제한하는 것은 무엇일까

높이가 h인 각 막대 i에 대해, 그 막대가 최솟값이 될 수 있는 가장 큰 직사각형은 왼쪽으로 h보다 짧은 첫 번째 막대가 나올 때까지, 오른쪽으로도 h보다 짧은 첫 번째 막대가 나올 때까지 확장됩니다. 너비는 right_boundary - left_boundary - 1이고 넓이는 h × width입니다.

이 관점으로 문제를 다시 표현할 수 있습니다. 각 막대의 이전 작은 원소(PSE)와 다음 작은 원소(NSE)를 찾는 것입니다. 이 값들은 단조 증가 스택으로 정확히 계산할 수 있습니다. 더 짧은 막대를 찾았기 때문에 막대 i를 꺼내는 순간, 현재 막대가 i의 NSE이고, 꺼낸 뒤 스택의 맨 위 원소가 i의 PSE입니다.

heights = [2, 1, 5, 6, 2, 3]
n = len(heights)

# Find PSE and NSE for each bar
pse = [-1] * n   # index of previous smaller element
nse = [n] * n    # index of next smaller element (default: beyond array)

# PSE
stack = []
for i in range(n):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    pse[i] = stack[-1] if stack else -1
    stack.append(i)

# NSE
stack = []
for i in range(n - 1, -1, -1):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    nse[i] = stack[-1] if stack else n
    stack.append(i)

max_area = 0
for i in range(n):
    width = nse[i] - pse[i] - 1
    area = heights[i] * width
    print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
    max_area = max(max_area, area)
print('Max area:', max_area)

단조 스택을 사용한 한 번의 순회 해법

앞서 설명한 두 번의 순회 방법도 동작하지만 한 번의 순회로 합칠 수 있습니다. 단조 증가 스택을 사용해 막대를 왼쪽에서 오른쪽으로 처리합니다. 막대 i가 스택의 맨 위 원소보다 짧으면 맨 위 원소를 꺼냅니다. 꺼낸 막대의 높이가 직사각형의 높이이고, 오른쪽 경계는 i이며, 왼쪽 경계는 새로운 스택 맨 위 원소 + 1입니다.

일반적인 방법은 heights의 끝에 특별한 표식값 0을 추가하는 것입니다. 이렇게 하면 자연스럽게 더 짧은 막대가 나타나지 않더라도 끝에서 모든 막대를 스택에서 꺼낼 수 있습니다. 이 표식값이 없으면 스택에 남은 원소를 처리하는 반복문 이후 정리 단계가 필요합니다.

def largest_rectangle(heights):
    stack = []   # monotonic increasing: indices of bars
    max_area = 0
    heights = heights + [0]  # sentinel: forces all bars to be popped

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]       # height of the rectangle
            width = i if not stack else i - stack[-1] - 1  # left boundary
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle([2, 4]))               # 4
print(largest_rectangle([1, 1]))               # 2
print(largest_rectangle([0, 9]))               # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3]))  # 16

한 번의 순회 알고리즘 추적

센티널을 포함한 [2, 1, 5, 6, 2, 3, 0]을 단계별로 추적해 보겠습니다.

i=0, h=2: 0을 넣습니다. 스택: [0]
i=1, h=1: 0을 꺼냅니다(h=2, 너비=1, 넓이=2). 스택이 비었으므로 1을 넣습니다. 스택: [1]
i=2, h=5: 5>1이므로 2를 넣습니다. 스택: [1,2]
i=3, h=6: 6>5이므로 3을 넣습니다. 스택: [1,2,3]
i=4, h=2: 3을 꺼냅니다(h=6,너비=4-2-1=1,넓이=6). 2를 꺼냅니다(h=5,너비=4-1-1=2,넓이=10★). 2>1이므로 멈춥니다. 4를 넣습니다. 스택: [1,4]
i=5, h=3: 3>2이므로 5를 넣습니다. 스택: [1,4,5]
i=6, 센티널 h=0: 모든 원소를 꺼내며 넓이를 계산합니다...

def largest_rectangle_trace(heights):
    stack = []
    max_area = 0
    hs = heights + [0]

    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            area = hs[top] * w
            print(f'  Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
            if area > max_area:
                max_area = area
                print(' *** NEW MAX ***', end='')
            print()
        print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
        stack.append(i)
    print(f'Max area: {max_area}')
    return max_area

largest_rectangle_trace([2, 1, 5, 6, 2, 3])

너비 계산: 왜 i - stack[-1] - 1일까

스택에서 막대 j를 꺼낼 때 다음을 알고 있습니다. j의 직사각형의 오른쪽 경계는 i입니다. 오른쪽에서 j보다 짧은 첫 번째 막대가 i이기 때문입니다. 왼쪽 경계는 꺼낸 뒤 스택에서 j 바로 아래에 있는 막대이며, 이를 k라고 하겠습니다. 따라서 너비는 i - k - 1입니다. 즉, k+1부터 i-1까지의 막대를 포함합니다.

꺼낸 뒤 스택이 비어 있다면 j의 직사각형은 왼쪽 끝까지 확장됩니다(인덱스 0). 너비는 간단히 i입니다(인덱스 0부터 i-1까지이며, 모두 heights[j] 이상입니다). 이는 다음과 같은 특별한 경우입니다. width = i if not stack else i - stack[-1] - 1

# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
#   stack after pop = [0, 1]   => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
#   stack after pop = [0]       => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.

def compute_boundaries(heights):
    hs = heights + [0]
    stack = []
    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            if stack:
                left = stack[-1] + 1
                width = i - stack[-1] - 1
            else:
                left = 0
                width = i
            print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
        stack.append(i)

compute_boundaries([2, 1, 5, 6, 2, 3])

이진 행렬에서 가장 큰 직사각형

최대 직사각형(LeetCode 85)은 히스토그램 문제를 2차원 이진 행렬로 확장한 문제입니다. 각 행에 대해 각 셀 위로 연속해서 이어지는 1의 개수를 높이로 계산합니다. 그러면 해당 행에 대한 히스토그램이 만들어집니다. 각 행의 히스토그램에 히스토그램에서 가장 큰 직사각형을 구하는 알고리즘을 적용합니다. 모든 행에서 얻은 최댓값이 답입니다.

이 방법은 2차원 문제를 반복되는 n개의 1차원 히스토그램 문제로 바꿉니다. m개 행과 n개 열을 가진 행렬의 시간 복잡도는 O(m × n)입니다. 각 행마다 히스토그램을 한 번 순회하고, 각 순회에는 O(n)이 걸립니다.

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    def hist_max_area(h):
        stack, area = [], 0
        for i, hh in enumerate(h + [0]):
            while stack and h[stack[-1]] > hh:
                top = stack.pop()
                w = i if not stack else i - stack[-1] - 1
                area = max(area, h[top] * w)
            stack.append(i)
        return area

    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, hist_max_area(heights[:]))
    return max_area

matrix = [['1','0','1','0','0'],
          ['1','0','1','1','1'],
          ['1','1','1','1','1'],
          ['1','0','0','1','0']]
print(maximal_rectangle(matrix))  # 6

히스토그램 문제의 경계 사례

다음과 같은 중요한 경계 사례를 처리해야 합니다.

모든 높이가 같음: 배열 전체가 하나의 직사각형을 이룹니다. 답 = n × 높이
단조 증가: 센티널이 나올 때까지 꺼내기가 발생하지 않습니다. 마지막 막대의 넓이가 최댓값입니다
막대 하나: 답 = height[0]
높이가 0인 막대: 자연스러운 센티널처럼 작동하여 히스토그램을 서로 독립적인 구간으로 나눕니다

끝에 센티널(0을 추가)을 두면 단조 증가인 경우에도 마지막에 남은 모든 막대를 꺼낼 수 있습니다. 센티널이 없으면 주 순회가 끝난 뒤 별도의 정리 반복문이 필요합니다.

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights = heights + [0]
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * w)
        stack.append(i)
    return max_area

# Edge cases
print(largest_rectangle([5, 5, 5, 5]))    # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5]))              # 5 (single bar)
print(largest_rectangle([0, 0, 0]))        # 0 (all zero)
print(largest_rectangle([3, 0, 3]))        # 3 (zero splits)

분할 정복 대안

히스토그램 문제는 분할 정복으로도 풀 수 있습니다. 최소 높이의 막대에서 나누고, 양쪽 절반을 재귀적으로 해결한 뒤, 최소 높이를 사용해 전체 너비를 덮는 직사각형과 비교합니다. 평균 시간 복잡도는 O(n log n)이지만, 정렬된 입력에서는 최악의 경우 O(n²)입니다.

단조 스택 방법은 최악의 경우에도 O(n)이므로 확실히 더 효율적입니다. 하지만 분할 정복 방법을 이해하면 문제에 대한 직관이 깊어지고, 어떤 구간에서든 최소 높이의 막대가 전체 너비 직사각형의 높이를 항상 제한하는 이유를 이해할 수 있습니다.

def largest_rectangle_dc(heights, lo=0, hi=None):
    if hi is None:
        hi = len(heights) - 1
    if lo > hi:
        return 0
    # Find the index of the minimum height in [lo, hi]
    min_idx = lo
    for i in range(lo, hi + 1):
        if heights[i] < heights[min_idx]:
            min_idx = i
    # Three options:
    # 1. Max rect entirely in left half
    # 2. Max rect entirely in right half
    # 3. Max rect spanning entire [lo, hi] with height = min
    full_width_area = heights[min_idx] * (hi - lo + 1)
    left_area  = largest_rectangle_dc(heights, lo, min_idx - 1)
    right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
    return max(full_width_area, left_area, right_area)

print(largest_rectangle_dc([2, 1, 5, 6, 2, 3]))  # 10

히스토그램 패턴: 부분 배열의 개수

같은 스택 기법을 사용하는 관련 문제로, 최솟값이 특정 목표값과 같은 히스토그램의 부분 배열 개수를 세는 문제가 있습니다. 각 막대의 PSE와 NSE를 계산한 다음 (i - pse[i]) × (nse[i] - i) 공식을 사용하면 됩니다. 이 공식은 막대 i가 최솟값인 부분 히스토그램의 개수를 셉니다.

이 ‘왼쪽 개수 × 오른쪽 개수’ 기법은 여러 LeetCode 문제에 등장합니다. 부분 배열 최솟값의 합(907), 모든 문자가 서로 다른 부분 문자열의 개수, 기여도 기법을 사용하는 문제 등이 그 예입니다. 단조 스택은 O(n)에 PSE와 NSE를 계산하므로 각 원소의 기여도를 O(1)에 구할 수 있습니다.

def sum_of_subarray_minimums(arr):
    n = len(arr)
    pse = [-1] * n   # previous strictly smaller element
    nse = [n] * n    # next smaller or equal element

    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        pse[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        nse[i] = stack[-1] if stack else n
        stack.append(i)

    MOD = 10**9 + 7
    total = 0
    for i in range(n):
        left_count = i - pse[i]          # subarrays where i is leftmost min
        right_count = nse[i] - i        # subarrays where i is the min
        total += arr[i] * left_count * right_count
    return total % MOD

print(sum_of_subarray_minimums([3, 1, 2, 4]))  # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3]))  # 444

실전 면접 팁

면접에서 히스토그램 문제를 만나면 다음 확인 목록을 따르세요:

명확히 하기: 높이가 0일 수 있는가요? 출력은 넓이, 인덱스 또는 개수 중 무엇인가요?
완전 탐색으로 시작하고 O(n²) 또는 O(n³) 시간 복잡도를 명시하세요
각 막대의 기여도는 양쪽에서 가장 가까운 더 짧은 막대까지의 범위에 따라 결정된다고 설명하세요
PSE/NSE → 단조 스택 → O(n) 해법을 소개하세요
코드를 간단하게 만들기 위한 감시값 기법(append 0)을 처리하세요
화이트보드에서 작은 예시를 추적하세요

자주 나오는 후속 질문은 2차원으로 확장하는 것(최대 직사각형)입니다. 이를 각각 O(n)인 n개의 히스토그램 문제로 줄여 전체 O(m×n)에 해결할 수 있음을 보여 주세요.

# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):  # sentinel forces final pops
        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

# Verify all test cases from earlier
test_cases = [
    ([2, 1, 5, 6, 2, 3], 10),
    ([6, 7, 5, 2, 4, 5, 9, 3], 16),
    ([1], 1),
    ([2, 0, 2], 2),
    ([], 0),
]
for heights, expected in test_cases:
    if not heights:
        result = 0
    else:
        result = largest_rectangle_in_histogram(heights)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: {heights} => {result} (expected {expected})')

부분 배열 범위의 합과 유사한 변형 문제

PSE/NSE 기법은 여러 LeetCode 문제에 일반화됩니다. 부분 배열 범위의 합(2104)은 모든 부분 배열에 대한 (최댓값 - 최솟값)의 합을 구하는 문제입니다. 이는 (부분 배열 최댓값의 합)에서 (부분 배열 최솟값의 합)을 뺀 것과 같으며, 두 합 모두 단조 스택을 사용해 O(n)에 계산할 수 있습니다. 대기열에서 볼 수 있는 사람의 수(1944)는 감소 스택을 사용하며, pop할 때마다 보이는 사람 한 명을 셉니다. 이 문제군을 알아보는 핵심은 '각 원소가 얼마나 멀리까지 지배할 수 있는가?'라는 문구를 발견하는 것입니다. 답은 항상 PSE/NSE와 단조 스택입니다.

def sum_subarray_ranges(nums):
    n = len(nums)
    # Sum of subarray max - sum of subarray min
    def contrib(arr, is_max):
        # Count contribution of each element as max (or min)
        n = len(arr)
        left = [0]*n; right = [0]*n
        stack = []
        for i in range(n):
            while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
                stack.pop()
            left[i] = i - (stack[-1] if stack else -1)
            stack.append(i)
        stack = []
        for i in range(n-1, -1, -1):
            while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
                stack.pop()
            right[i] = (stack[-1] if stack else n) - i
            stack.append(i)
        return sum(arr[i] * left[i] * right[i] for i in range(n))
    return contrib(nums, True) - contrib(nums, False)

print(sum_subarray_ranges([1, 2, 3]))    # 4
print(sum_subarray_ranges([1, 3, 3]))    # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1]))  # 59

빠른 확인

이 레슨에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.

레슨 복습

이 레슨에서 배운 내용은 다음과 같습니다. 각 막대를 포함하는 가장 큰 직사각형의 경계는 양쪽에서 가장 가까운 더 짧은 막대(PSE 및 NSE)에 의해 정해집니다. 단조 증가 스택은 막대가 빠질 때 양쪽 경계를 모두 찾으면서 한 번의 O(n) 순회로 모든 PSE/NSE 경계를 계산합니다. 또한 감시값 0을 추가하면 스택에서 모든 막대를 꺼낼 수 있어 코드가 하나의 반복문으로 단순해집니다. 다음에는 단조 덱을 사용해 슬라이딩 윈도 최댓값을 O(n)에 구합니다.

자주 묻는 질문

“히스토그램에서 가장 큰 직사각형” 강의는 무료인가요?

네 — “히스토그램에서 가장 큰 직사각형” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“히스토그램에서 가장 큰 직사각형”에서 뭘 배우나요?

단조 스택으로 왼쪽 경계를 추적하고 한 번의 순회로 히스토그램 안에 들어가는 직사각형의 최대 넓이를 계산합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

“히스토그램에서 가장 큰 직사각형” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← DSA Interview Prep(으)로 돌아가기