각 원소보다 오른쪽에 있는 첫 큰 값을 찾으려 합니다. 단조 스택은 어떻게 중복 탐색을 줄이나요?

아직 답을 못 찾은 원소의 인덱스를 단조 순서로 스택에 유지하고 새 값이 그 조건을 만족하면 여러 원소의 답을 한 번에 확정합니다. 모든 오른쪽 구간을 다시 훑는 대신 각 원소가 제한된 횟수로 들어가고 나옵니다.

동작 원리와 전제

다음 큰 값을 찾는다면 새 값이 스택 위 값보다 클 때 pop한 원소의 답이 됩니다. 같은 값을 큰 것으로 볼지 크거나 같은 것으로 볼지 비교 조건을 고정합니다. 값만 저장하면 위치·거리 계산을 잃을 수 있어 인덱스를 저장합니다.

선택과 실패 처리

각 원소는 한 번 push·한 번 pop되므로 내부 while이 있어도 전체는 선형일 수 있습니다. 이것은 개별 반복이 항상 상수 시간이라는 뜻이 아니라 연산열 전체의 상환 분석입니다. 원형 배열이나 왼쪽 질의는 순회·종료 규칙이 달라집니다.

구체적인 사례와 검증

입력 [2,1,3]에서 3을 만나면 스택의 1과 2를 꺼내 두 원소의 다음 큰 값이 3임을 확정할 수 있습니다. 그 사이 더 이른 큰 값이 있었다면 이미 pop됐어야 하므로 현재 값이 첫 적합 값이라는 불변식입니다. 동일값을 허용하는 조건은 >와 >=에서 달라져 중복 데이터 테스트가 중요합니다. pop한 인덱스는 다시 스택에 넣지 않으므로 중첩 while의 전체 횟수가 선형으로 제한됩니다. 개별 새 값 하나가 많은 원소를 pop할 수 있어 한 반복의 최대 비용과 전체 상환 비용은 구분해야 합니다. 입력을 스트림으로 받을 때 결과를 언제 확정할 수 있는지도 명시합니다.

증가·감소·동일값·빈 배열·한 원소를 단순 이중 루프와 비교합니다. 스택에 남은 원소의 부재 결과를 명시합니다. 단조성 불변식과 pop 시점이 왜 첫 적합 원소인지 설명할 수 있어야 합니다.