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