핵심 정리
| 형태 | 스택에 남기는 값 | pop 조건 | 대표 문제 |
|---|---|---|---|
| 증가 스택 | 값이 오름차순 | 새 값이 더 작음 | 다음 작은 값 |
| 감소 스택 | 값이 내림차순 | 새 값이 더 큼 | 다음 큰 값 |
| index 스택 | 위치 저장 | 경계 발견 시 계산 | 거리, 폭, 직사각형 |
csharp
int[] answer = new int[n];
Array.Fill(answer, -1);
var stack = new Stack<int>(); // index
for (int i = 0; i < n; i++)
{
while (stack.Count > 0 && arr[stack.Peek()] < arr[i])
{
int index = stack.Pop();
answer[index] = arr[i];
}
stack.Push(i);
}구조
단조 스택은 스택 안의 값이 한 방향으로 정렬된 상태를 유지합니다. 새 값이 들어왔을 때 이 규칙을 깨는 원소를 pop하면서, 그 순간 “가장 가까운 더 큰 값”이나 “가장 가까운 더 작은 값”을 확정합니다.
text
arr: 2 1 5 3 4
5가 들어오는 순간:
- 1의 다음 큰 값은 5
- 2의 다음 큰 값도 5각 원소는 한 번 push되고 한 번 pop되므로 전체 시간 복잡도는 O(n)입니다. 겉으로는 중첩 while처럼 보이지만, 같은 원소가 여러 번 pop되지 않습니다.
값보다 index를 저장하는 이유
대부분의 문제에서는 값뿐 아니라 위치 차이, 왼쪽 경계, 오른쪽 경계가 필요합니다. 그래서 스택에는 값을 직접 넣기보다 index를 넣고, 비교할 때 arr[stack.Peek()]처럼 원본 배열을 참조합니다.
csharp
int distance = i - index;같은 값이 있을 때 <를 쓸지 <=를 쓸지도 index 저장 방식에서 명확히 정해야 합니다. 중복 값을 같은 높이로 유지할지, 새 값으로 교체할지가 답의 기준을 바꿀 수 있습니다.
문제별 형태
| 문제 | 스택 방향 | 확정되는 순간 |
|---|---|---|
| 다음 큰 원소 | 감소 스택 | 더 큰 값이 오른쪽에서 등장 |
| 다음 작은 원소 | 증가 스택 | 더 작은 값이 오른쪽에서 등장 |
| 주식 가격 하락까지 시간 | 증가/감소 조건 변형 | 가격이 기준을 깨는 순간 |
| histogram 최대 직사각형 | 증가 스택 | 낮은 막대가 오른쪽 경계가 됨 |
| 일일 온도 | 감소 스택 | 더 따뜻한 날이 등장 |
histogram 문제에서는 pop되는 막대의 높이가 직사각형 높이가 되고, 현재 index가 오른쪽 경계가 됩니다. 왼쪽 경계는 pop 이후 스택 top으로 계산합니다.
주의할 점
단조 스택은 가까운 더 큰 값이나 더 작은 값처럼 “한쪽 방향에서 처음 만나는 경계”를 찾을 때 강합니다. 모든 쌍을 비교해야 하는 문제나 정렬 순서를 완전히 유지해야 하는 문제에는 맞지 않습니다.
마지막까지 스택에 남은 index는 오른쪽에서 조건을 만족하는 원소를 만나지 못한 상태입니다. 기본값을 -1, 0, 배열 끝까지의 거리 중 무엇으로 둘지 문제 요구에 맞춰 처리하세요.