Medium · Monotonic Stack
Understand → Visualise → Practice.
For each day, return how many days pass before a warmer temperature, or 0 if none does.
A stack of indices with decreasing temperatures holds the days still waiting for something warmer. A warmer day answers every colder day on top of the stack.
For each day i, look at the stack top.
While the top day is colder than day i, pop it and set its answer to i − top.
Push day i; days left on the stack at the end keep answer 0.
O(n) time and O(n) space.
Comparing each day with every later day is O(n²).
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.