Keep a stack that only ever increases (or decreases) to find the next greater element.
The tell: 'Next greater', 'previous smaller', 'span', histogram areas, or temperatures.
Reach for it when
Next greater / next smaller element
Largest rectangle in a histogram
Daily temperatures
Trapping rain water (stack variant)
Removing k digits to get the smallest number
Reference implementation
next_greater — decreasing stack of indices
def next_greater(nums: list[int]) -> list[int]:
"""result[i] = next element to the right greater than nums[i], else -1."""
result = [-1] * len(nums)
stack: list[int] = [] # indices, values decreasing
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
result[stack.pop()] = value
stack.append(i)
return result
Complexity: O(n) — every index is pushed once and popped at most once.
What goes wrong
Storing values instead of indices, which loses the position you need to write back to.
Using `<=` vs `<` carelessly — it changes behaviour on duplicates and is often the whole bug.
Forgetting the sentinel (a trailing 0 in histogram problems) so the stack never drains.