Monotonic Stack
Keep a stack whose values stay sorted. Pop everything the new element dominates, and each pop resolves one answer.
Stacks & QueuesO(n), every index is pushed and popped onceNew25 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
next greater element
largest rectangle
daily temperatures
span problems
The template
Get this into muscle memory, then adapt the condition per problem.
const st: number[] = [];
for (let i = 0; i < n; i++) {
while (st.length && a[st[st.length - 1]] < a[i]) {
const j = st.pop()!;
ans[j] = i - j;
}
st.push(i);
} Watch Monotonic Stack (Next Greater)If you are stuck
The generic hint ladder for this pattern, in order.
- 1For each element you want the nearest bigger or smaller neighbour.
- 2Elements that are smaller than the current one can never be the answer for anything further right.
- 3Store indices, not values, so you can compute distances.
Drill it
Every problem in the bank that uses this pattern.
0 / 25 solved