단조 스택 패턴
단조 스택을 적용해 O(n)에 daily-temperatures, largest-rectangle-in-histogram, next-greater-element 문제를 해결합니다.
단조 스택 패턴은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
단조 스택이란 무엇인가요?
단조 스택은 요소들 사이에서 정렬 불변식을 유지하는 스택입니다. 오름차순 단조 스택은 아래에서 위로 갈수록 요소가 증가하고, 내림차순 단조 스택은 아래에서 위로 갈수록 요소가 감소합니다. 새 요소가 불변식을 위반하면 불변식이 복원될 때까지 요소를 제거한 다음 새 요소를 push합니다.
이 간단한 메커니즘을 사용하면 순진하게 구현할 경우 O(n²)의 중첩 반복문이 필요한 ‘가장 가까운 더 큰 요소’와 ‘가장 가까운 더 작은 요소’ 질의를 O(n)에 해결할 수 있습니다.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)다음으로 큰 요소(LeetCode 496)
각 요소에 대해 오른쪽에 있는 요소 중 처음으로 만나는 엄 strictly 큰 요소를 찾습니다. 무차별 대입 방식은 각 위치에서 오른쪽으로 훑으므로 O(n²)이 걸립니다. 단조 스택 방식에서는 인덱스를 내림차순 스택에 저장합니다. 더 큰 요소를 만나면 값이 더 작은 인덱스를 모두 제거합니다. 이 인덱스들의 ‘다음으로 큰 요소’가 현재 요소이기 때문입니다. 스택에 남은 인덱스에는 다음으로 큰 요소가 없으므로 답은 -1입니다.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]원형 배열에서의 다음으로 큰 요소
LeetCode 503 ‘다음으로 큰 요소 II’: 배열을 원형으로 취급한다는 점만 다른 동일한 문제입니다. 배열의 끝에 도달하면 처음으로 돌아가 확인합니다. 핵심 방법은 배열을 두 번 순회하는 것입니다(인덱스 0부터 2n-1까지). 원래 배열에 접근할 때는 i % n을 사용합니다. 중복 처리를 피하려면 [0, n-1] 범위의 인덱스만 push합니다.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]일일 기온: 전체 풀이
LeetCode 739 다시 보기: 각 날짜에 대해 더 따뜻한 날이 올 때까지 며칠이 걸리는지 구합니다. 단조 스택에는 기온이 내림차순인 날짜의 인덱스를 저장합니다. 더 따뜻한 날 i를 찾으면 스택에서 더 서늘한 날의 인덱스 j를 모두 제거하고 result[j] = i - j를 기록합니다. 스택에 남은 날짜에는 더 따뜻한 날이 없었던 것이므로 결과는 0으로 유지됩니다.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]이전의 더 작은 요소
‘이전의 더 작은 요소’ 질의는 각 요소에 대해 왼쪽에서 가장 가까운 더 작은 값이 무엇인지 묻습니다. 왼쪽에서 오른쪽으로 처리하면서 오름차순 단조 스택을 사용하십시오. 인덱스 i를 push하기 전에 스택의 top이 이전의 더 작은 요소입니다. 이전에 더 큰 요소가 삽입될 때 nums[i]보다 큰 모든 요소가 이미 제거되었기 때문입니다.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]히스토그램에서 가장 큰 직사각형
LeetCode 84 ‘히스토그램에서 가장 큰 직사각형’: 인덱스를 저장하는 단조 오름차순 스택을 사용합니다. 각 막대에 대해 현재 막대보다 높이가 큰 막대를 모두 제거합니다. 제거된 각 막대 h에 대해 오른쪽 경계는 현재 인덱스 i이고, 왼쪽 경계는 새 스택 top + 1입니다(스택이 비어 있으면 0). 넓이는 h × (right - left)입니다. 높이가 0인 보초 값을 끝에 추가하면 남아 있는 모든 막대가 마지막에 제거됩니다.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1최대 직사각형(LeetCode 85)
LeetCode 85 ‘최대 직사각형’은 히스토그램 문제를 2차원 이진 행렬로 확장한 문제입니다. 각 행에 대해 누적된 막대 높이를 계산합니다. matrix[row][col] == '1'이면 해당 칸을 포함하여 위쪽에 연속으로 있는 1의 개수가 높이가 됩니다. 그런 다음 각 행의 높이 배열에 ‘히스토그램에서 가장 큰 직사각형’ 알고리즘을 적용합니다. m×n 행렬에서 시간 복잡도는 O(m × n)입니다.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6빗물 받기: 스택 방식
LeetCode 42 ‘빗물 받기’를 스택으로 풉니다. 인덱스를 내림차순 스택에 저장합니다. 더 높은 막대를 만나면 골짜기가 생깁니다. 골짜기의 바닥을 제거한 뒤, 물이 차는 너비를 (current_index - stack_top - 1)로 계산하고 높이를 (min(current_bar, new_stack_top_bar) - valley_height)로 계산합니다. 모든 기여도를 더합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9단조 스택 문제 알아보기
단조 스택이 적합하다는 신호는 다음과 같습니다. 문제에서 다음 또는 이전의 더 큰 요소나 더 작은 요소를 요구하거나, 각 요소의 답이 특정 방향에 있는 요소에 의존하거나, 순진한 O(n²) 풀이가 각 요소마다 왼쪽 또는 오른쪽을 훑는 경우입니다. 스택에는 미래 요소의 답이 될 가능성이 있는 후보를 저장하고, 더 나은 후보가 도착하는 즉시 기존 후보를 버립니다.
코딩을 시작하기 전에 오름차순(다음 또는 이전의 더 작은 요소를 찾을 때)인지 내림차순(다음 또는 이전의 더 큰 요소를 찾을 때)인지, 그리고 어느 방향으로 처리할지 항상 결정하십시오.
분할 상환 O(n) 분석
단조 스택 알고리즘은 for 반복문 안에 while 반복문이 있기 때문에 처음에는 O(n log n) 또는 O(n²)처럼 보입니다. 하지만 각 요소는 최대 한 번 push되고 최대 한 번 pop됩니다. 전체 push 연산 횟수는 n이고 전체 pop 연산 횟수도 최대 n입니다. 따라서 모든 반복에 걸친 전체 작업량은 2n번의 연산, 즉 O(n) 분할 상환 시간입니다. O(n²)이 아닙니다.
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*n요약: 단조 스택 불변식 선택
질의에 따라 스택의 방향을 선택하십시오. 다음으로 큰 요소에는 내림차순 스택을 사용하고, 현재 요소가 더 크면 제거합니다. 다음으로 작은 요소에는 오름차순 스택을 사용하고, 현재 요소가 더 작으면 제거합니다. 가장 큰 직사각형에는 오름차순 스택을 사용하고 더 짧은 막대가 나타나면 제거합니다. 슬라이딩 윈도 최댓값에는 내림차순 덱을 사용하고 양쪽 끝에서 제거합니다.
코딩 전에 주석으로 불변식을 작성하면 로직이 명확해지고 디버깅 속도도 빨라집니다.
빠른 확인
이번 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 확인해 보십시오.
학습 내용 복습
이번 학습에서 다음을 배웠습니다. 단조 스택은 새 요소를 push하기 전에 불변식을 위반하는 요소를 제거하여 정렬 불변식을 유지합니다. 내림차순 스택은 다음으로 큰 요소 질의에 답하고, 오름차순 스택은 다음으로 작은 요소 질의에 답합니다. 또한 각 요소가 최대 한 번 push되고 pop되므로 전체 시간은 O(n) 분할 상환입니다. 다음에는 스택으로 큐를 구현하고 큐로 스택을 구현합니다.
AI 튜터와 함께 Coding Interview Prep을(를) 배우세요 — 무료
브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.
- 코스
- 90
- 레슨
- 360
자주 묻는 질문
“단조 스택 패턴” 강의는 무료인가요?
네 — “단조 스택 패턴” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“단조 스택 패턴”에서 뭘 배우나요?
단조 스택을 적용해 O(n)에 daily-temperatures, largest-rectangle-in-histogram, next-greater-element 문제를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“단조 스택 패턴” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 스택 구현과 활용
- 큐 구현과 덱
- 단조 스택 패턴
- 스택과 큐의 상호 시뮬레이션