단조 스택: 다음으로 큰 원소

각 숫자에 대해 오른쪽에서 처음 만나는 더 큰 값을 찾으려고 합니다. 완전 탐색은 O(n 제곱)이지만 단조 스택을 사용하면 한 번의 순회로 해결할 수 있습니다.

단조 스택은 값을 정렬된 순서로 유지합니다. 여기서는 내림차순으로 유지하므로 그 순서가 깨지는 순간 정답을 찾았다는 것을 알 수 있습니다.

그대로의 숫자 대신 인덱스를 넣습니다. 그러면 더 큰 원소가 나타났을 때 어느 위치에 정답을 기록해야 하는지 정확히 알 수 있습니다.

배열을 한 번 순회합니다. 각 인덱스에서 이미 해결된 항목을 꺼내거나, 나중을 위해 현재 인덱스를 넣습니다.

현재 값이 맨 위 인덱스의 값보다 큰 동안에는 해당 맨 위 항목이 마침내 다음으로 큰 원소를 찾은 것입니다.

맨 위 인덱스를 꺼내고 그 정답을 현재 값으로 설정합니다. 각 인덱스는 정확히 한 번만 해결되므로 전체 작업량이 선형으로 유지됩니다.

더 작은 모든 항목을 처리한 뒤 현재 인덱스를 넣어 나중에 자신보다 큰 원소가 나타날 때까지 기다리게 합니다.

마지막까지 스택에 남은 인덱스는 더 큰 값을 만나지 못한 것입니다. 이들의 기본값인 -1을 유지하며, 더 큰 값이 없다는 뜻입니다.

각 인덱스는 한 번 넣고 한 번 꺼냅니다. 내부 while 반복문이 있더라도 전체 순회에서 총 작업량은 선형으로 유지됩니다.

대신 다음으로 작은 원소가 필요하신가요? 비교를 크다에서 작다로 뒤집어 스택을 오름차순으로 유지하면 됩니다.

구간 질의, 주가, 히스토그램 넓이 문제에서 모두 이 아이디어를 재사용할 수 있습니다. 단조 스택은 기억해 둘 가치가 있는 대회의 핵심 패턴입니다.

단조 스택으로 다음으로 큰 원소를 구하고 있습니다. 전체 시간이 선형인 이유는 무엇일까요?

인덱스로 이루어진 내림차순 단조 스택을 사용해 O(n)에 다음으로 큰 원소를 찾았습니다. 이 패턴은 다양한 구간 문제를 해결하는 데 도움이 됩니다. 🚀