A monotonic stack stays ordered. When a new value makes older candidates useless, those candidates are removed immediately.
Find the next warmer day
For each temperature, keep indexes of days still waiting for something warmer. A warmer value resolves every smaller temperature on top of the stack.
- Store indexes when positions matter.
- Pop while the new value answers the top candidate.
- Leave unresolved candidates on the stack.
- Each item is pushed and popped at most once.
One pass replaces repeated searching
def next_greater(numbers):
answer = [-1] * len(numbers)
stack = []
for index, number in enumerate(numbers):
while stack and numbers[stack[-1]] < number:
old_index = stack.pop()
answer[old_index] = number
stack.append(index)
return answer
print(next_greater([2, 1, 4, 3]))
# [4, 4, -1, -1]Although there is a loop inside a loop, the total work is O(n) because no index can be removed twice.
This pattern appears in next-greater questions, histogram areas, stock spans, and visibility problems.
Your tiny challenge
For 3, 2, 5, 4, list the values on the stack after each number arrives. Which old values does 5 remove?