단조 스택은 값을 정렬해 두는 자료구조가 아니라, 현재 값이 답을 확정한 과거 위치를 다시 검사하지 않도록 보류 목록을 압축하는 방법입니다. 먼저 답의 방향과 동점 규칙을 정한 뒤, 어떤 후보를 영구히 버릴 수 있는지 추적하면 구현과 복잡도를 함께 설명할 수 있습니다.
위치별 오른쪽 재탐색과 반복 비용
배열 [2,1,2,4,3]에서 각 값보다 오른쪽에 있는 첫 번째 더 큰 값의 인덱스를 찾겠습니다. 매 위치마다 끝까지 훑으면 감소 배열에서 검사량이 n-1+n-2+…로 늘어납니다.
대신 아직 큰 값을 못 찾은 위치를 기억해 두고 새 값이 왔을 때 그중 답이 정해지는 항목만 꺼낼 수 있습니다. 이때 스택의 값이 한 방향의 순서를 유지하므로 단조 스택이라고 부릅니다. 스택에 값이 아니라 인덱스를 넣어야 답의 위치와 거리를 함께 구할 수 있습니다.
미해결 인덱스와 단조 스택 불변식
왼쪽에서 오른쪽으로 순회합니다. 스택에는 아직 답이 없는 인덱스가 증가하는 순서로 들어 있고, 그 위치의 값은 아래에서 위로 비증가합니다. 새 값이 위 값보다 크면 위 항목의 답을 새 위치로 확정해 제거합니다.
| 입력 위치·값 | 제거되어 답이 정해진 위치 | 처리 뒤 스택의 인덱스 | 대응 값 |
|---|---|---|---|
| 0·2 | 없음 | [0] | [2] |
| 1·1 | 없음 | [0,1] | [2,1] |
| 2·2 | 1의 답=2 | [0,2] | [2,2] |
| 3·4 | 2의 답=3, 0의 답=3 | [3] | [4] |
| 4·3 | 없음 | [3,4] | [4,3] |
최종 답은 [3,2,3,NONE,NONE]입니다. 위치 0의 2는 위치 2의 같은 값 2로 해결되지 않습니다. “더 크다”와 “크거나 같다”의 요구가 다른 지점입니다.
그림을 글로 읽기
- 스택 [0,2]: 두 위치의 값은 2 · 새 위치 3의 값은 4
- 위 위치 2 제거: answer[2]=3
- 위 위치 0 제거: answer[0]=3
- 새 위치 3 삽입: 스택 [3], 값 [4]
- 스택 [0,2] → 위 위치 2 제거: 2 < 4
- 위 위치 2 제거 → 위 위치 0 제거: 다음 2 < 4
- 위 위치 0 제거 → 새 위치 3 삽입: 미해결로 등록
현재 값과 오른쪽 첫 큰 위치의 확정 근거
스택에 남아 있는 위치 j는 아직 오른쪽에서 더 큰 값을 만나지 못한 미해결 후보입니다. 예제에서 i=3의 값 4가 오면 스택 위의 위치 2와 그 아래의 위치 0이 차례로 pop되는데, 두 위치 모두 그보다 앞에서 더 큰 값을 만났다면 이미 빠져 있었어야 합니다. 따라서 값 4가 있는 위치 3은 위치 2와 0 각각에 대해 오른쪽의 첫 큰 위치입니다.
반대로 스택 위 값이 현재 값 이상이면 그 아래 값은 더 크거나 같으므로 현재 값이 답이 될 수 없습니다. 단조성이 이 관계를 보장하므로 여기서 멈출 수 있고, 모든 과거 인덱스를 다시 훑을 필요가 없습니다.
슈도코드와 동점 정책
구현 전에 답을 값, 인덱스, 거리 중 무엇으로 반환할지와 동점 허용 여부를 테스트 입력으로 고정합니다. 예를 들어 [2,2,3]에서 엄격한 큰 값의 인덱스는 [2,2,NONE]이고, 크거나 같은 값의 인덱스는 [1,2,NONE]가 되므로 비교 연산 하나가 API 의미를 바꿉니다.
nextGreaterIndex(a):
answer = [NONE] * length(a)
stack = []
for i from 0 to length(a)-1:
while stack not empty and a[stack.last] < a[i]:
j = stack.pop()
answer[j] = i
stack.push(i)
return answer
크거나 같은 첫 값을 찾으려면 비교를 <=로 바꿉니다. 이때 같은 값도 답이 되어 제거되므로 스택의 값은 엄격히 감소합니다. 원하는 답이 값이라면 인덱스를 얻은 뒤 배열을 읽고, 거리가 필요하면 answer[j]-j를 구합니다. NONE을 유효한 0번 인덱스와 혼동하면 안 됩니다.
비교는 일관된 순서를 가져야 합니다. NaN처럼 비교가 일반 전순서와 다른 입력을 허용한다면 별도 정책이 필요합니다. 스트림이 끝나지 않았다면 남은 항목은 아직 답을 모르는 상태이지 영원히 답이 없다고 확정된 상태가 아닙니다.
push·pop 상환 분석과 선형 전체 비용
각 인덱스는 정확히 한 번 push되고 최대 한 번 pop됩니다. 전체 pop 횟수는 n 이하이므로 전체 시간은 O(n), 스택과 답 공간은 O(n)입니다. 이것은 개별 입력 하나가 O(1)이라는 뜻은 아닙니다. 긴 감소 구간 뒤 매우 큰 값 하나가 오면 그 한 단계가 O(n)개를 제거할 수 있습니다.
이런 상환 분석은 입력이 무작위라는 가정을 요구하지 않습니다. 어떤 유한 입력에서도 총 push·pop 횟수로 비용을 제한합니다. 실시간 처리의 개별 지연 상한과 전체 처리량은 여전히 별도입니다.
적용 범위별 정확성 재증명
실패를 진단할 때는 먼저 pop 조건, 인덱스 저장 여부, 남은 스택의 최종 의미를 확인합니다. 원형 배열이나 이전 큰 원소 문제에 같은 슈도코드를 복사하면 순회 횟수와 답 확정 시점이 달라지므로, 작은 기준 구현과 결과를 대조한 뒤에만 재사용을 결정해야 합니다.
원형 배열에서는 한 바퀴 뒤 앞부분도 오른쪽 후보가 됩니다. 두 번 순회하되 답 대상 등록과 종료를 제한하는 등 별도 규칙이 필요합니다. 가장 큰 값 자체가 아니라 합·중앙값·임의 구간 질의라면 같은 제거 논리를 적용할 수 없습니다.
테스트는 증가·감소·동일값·빈 배열·한 항목과 [2,1,2,4,3]을 단순 이중 루프와 비교합니다. 매 단계 스택 인덱스가 증가하고 값이 비증가하는지, pop된 인덱스가 다시 등록되지 않는지도 검사합니다. 자료구조 이름보다 무엇을 영구히 버려도 되는가가 정확성의 핵심입니다.