A stack that you keep sorted (always increasing or always decreasing) by popping items that can no longer be the answer. Each item is pushed and popped once.
Used for
stack: 2
stack: 2, 1
5 > 1 and 5 > 2
stack: 5, 3
6 > 3 and 6 > 5
The stack holds 8, 4 and the next number is 6. What happens?
Not quite. 6 is bigger than 4, so 4 is answered and popped. 6 is smaller than 8, so 8 keeps waiting and 6 is pushed above it.
Step 1 of 7
Goal: for each number, find the next bigger number to its right. Comparing every number with everything after it is slow. Instead keep a stack of numbers that are still waiting for a bigger one.
Step 2 of 7
Take 2. Nothing to compare yet, so it waits on the stack.
Step 3 of 7
Take 1. It is smaller than the waiting 2, so it cannot be anyone's answer. It waits too, on top.
Step 4 of 7
Take 5. It is bigger than 1, so 5 is the answer for 1. Pop 1. It is bigger than 2 as well, so pop 2 too. Then 5 waits.
Step 5 of 7
Take 3. Smaller than 5, so it waits on top.
Step 6 of 7
Take 6. It beats 3 and 5, so both get answer 6. Whatever is left never found a bigger number. Each number is pushed once and popped once, so it is one pass. The stack stays in decreasing order, which is why this is called a monotonic stack.
Step 7 of 7
Your turn.
StackValid Parentheses ProblemRain Terraces (Trapping Rain Water) Problem
function nextGreater(a) { const out = Array(a.length).fill(-1), st = []; for (let i = 0; i < a.length; i++) { while (st.length && a[st.at(-1)] < a[i]) out[st.pop()] = a[i]; st.push(i); } return out;}