For each day, how many days until a warmer temperature? Return an array of waits (0 if none).
The monotonic-stack trick for 'next greater element' in O(n).
Keep a stack of indices whose warmer-day is still unknown, kept decreasing. When today is warmer than the temperature at the stack top, we've just found that day's answer — pop and record the gap. Each index is pushed/popped once → O(n), beating the O(n²) scan. The invariant is what makes it click: the stack always holds a strictly-decreasing run of temperatures, so the first day taller than today resolves possibly many pending days in a burst. This is the canonical 'next greater element' template — the same skeleton solves stock-span, largest-rectangle-in-histogram, and trapping-rain-water.
'Next greater/smaller element', 'span until a bigger value' → monotonic stack.
Time O(n) · Space O(n)