People in a queue looking for the next taller person ahead: when someone tall arrives, everyone shorter waiting behind them gets their answer and leaves.
Clues that point here
→ "Next greater" or "next smaller" element
→ "How many days until a warmer temperature"
→ Largest rectangle in a histogram
→ Stock span
Not this pattern when
✕ You need the max of a sliding window (monotonic deque)
✕ Simple max over the whole array
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Monotonic Stack · template
int[] answer = new int[nums.length];
Arrays.fill(answer, -1);
Deque<Integer> stack = new ArrayDeque<>(); // holds indexes, values decreasing
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
answer[stack.pop()] = nums[i]; // nums[i] is their next greater
}
stack.push(i);
}
return answer;