Description

A monotonic stack is a LIFO Stack whose contents are kept entirely increasing or entirely decreasing. Reach for it on "next/previous greater or smaller element" questions, since each pop is the moment an earlier item finds its answer.
?

Reach for when

Runtime

O(n)

Visualization

Pseudocode

stack = []
for item in items:
	while item > (or <) top of stack:
		pop and do action
	stack.push(item)

Code

def daily_temperatures(temps):
	answer = [0] * len(temps)
	stack = []
	for i, t in enumerate(temps):
		while stack and t > temps[stack[-1]]:
			j = stack.pop()
			answer[j] = i - j
		stack.append(i)
	return answer