Pattern 04
Monotonic Stack
Keep unresolved positions in value order so a new item can answer several of them at once.
Recognize it
Read the constraints before choosing the technique
Next or previous greater/smaller item
Each position waits for the first later item that defeats it.
Distance to the next qualifying item
The stack should store positions so their difference is available.
The slow solution scans rightward from every index
A stack can preserve only candidates that still lack an answer.
Histogram width or boundary problems
Popping can reveal both the first smaller boundary and the previous surviving boundary.
Cases that look similar but need another approach
The maximum of a moving window is required
Expired items must also leave from the front, which a stack cannot do.
Items are compared with a running total rather than one another
Nothing causes unresolved candidates to be popped.
Every greater item must be returned
Popping after one answer would discard information the output still needs.
Reasoning
The ideas the code depends on
The stack is ordered because weaker candidates leave
For a decreasing stack, a larger incoming value repeatedly removes smaller top values. Once it stops, the remaining top and everything below it are at least as large.
Store indices, not just values
The index gives back both nums[index] and a distance such as current − index. The value alone cannot recover position.
Nested loops do not make this quadratic
Each index is pushed once and popped at most once. The total number of stack operations is at most 2n.
Procedure
Turn the invariant into a repeatable process
- 01
Visit positions from left to right.
- 02
While the stack is non-empty and the current value answers its top, pop that position.
- 03
Write the popped position’s value, distance, or boundary answer.
- 04
Push the current position because it now waits for a future answer.
- 05
Leave the default result for any positions still unresolved at the end.
Common forms of the pattern
Every index enters the stack once and can leave it only once, so all executions of the inner while loop total at most n.
Implementation
Worked form
Daily temperatures
For each day, return how many days pass before a warmer temperature; return zero when none exists.
Daily temperatures
int[] daysUntilWarmer(int[] temperature) {
int[] answer = new int[temperature.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temperature.length; i++) {
while (!stack.isEmpty()
&& temperature[i] > temperature[stack.peek()]) {
int earlier = stack.pop();
answer[earlier] = i - earlier;
}
stack.push(i);
}
return answer;
}def days_until_warmer(temperature):
answer = [0] * len(temperature)
stack = []
for i, current in enumerate(temperature):
while stack and current > temperature[stack[-1]]:
earlier = stack.pop()
answer[earlier] = i - earlier
stack.append(i)
return answervector<int> daysUntilWarmer(const vector<int>& temperature) {
vector<int> answer(temperature.size());
stack<int> st;
for (int i = 0; i < temperature.size(); i++) {
while (!st.empty() && temperature[i] > temperature[st.top()]) {
int earlier = st.top(); st.pop();
answer[earlier] = i - earlier;
}
st.push(i);
}
return answer;
}Common implementation mistakes
- Peeking before checking that the stack is non-empty
- Storing values when the answer requires distance
- Using < where duplicates require <=, or the reverse
- Calling the algorithm O(n²) merely because the loops are nested
Problem family
What stays the same—and what changes
These are not five unrelated solutions. Each problem preserves the movement rule and changes one part of the state or answer.
Next Greater Element
EasyWrite the incoming value rather than a distance.
Stock Span
MediumPop previous smaller prices and answer from the surviving boundary.
Remove K Digits
MediumPop larger earlier digits while removals remain.
Largest Rectangle in Histogram
HardUse both boundaries exposed when a bar is popped.
Trapping Rain Water
HardTreat a popped bar as the bottom of a basin.
Check yourself