Frame
Monotonic Stack
배열에서 단조 스택을 활용해 O(N)으로 다음 더 큰(혹은 작은) 값을 찾는 패턴과 구현 팁을 정리
Oct 20, 2025 — monotonic-stack
- 경험하지 못하면 바로 생각하기는 힘든 유형.
- Array 에서 자신의 값보다 큰 값 (혹은 작은 값)을 찾는 경우에
O(N)시간으로 해결할 수 있는 방법. - stack 에 현재 값을
[ index, value ]형태로 저장하면서, stack top 의 값과 현재 값을 비교해서 원하는 조건을 만족하는 경우에 stack pop 하여 이전 저장된 결과로부터 계산을 수행.
const fn = (array) => { const N = array.length;
const result = Array(N).fill(0); const stack = [];
for (const [ index, value ] of array.entries()) { // found larger value while (stack.length && stack.at(-1)[1] < value) { // 조건에 따라서 더 큰 값혹은 더 작은 값을 찾는다. // while (stack.length && stack.at(-1)[1] > value) { const [ lastIndex, lastValue ] = stack.pop(); result[lastIndex] = ... } // push current value to stack stack.push([ index, value ]) } return result;}