Why it works
- A day waits on the stack until the first warmer day comes. That day pops it at once, so the distance between the two is exactly its wait.
- Every day on the stack is not warmer than the one under it: a warmer day would have popped it. So when today is not warmer than the top, it is not warmer than anything below it either, and the loop can stop.
- An equal temperature does not pop: the problem asks for a strictly warmer day. Days still on the stack at the end never got one and keep their 0.
Complexity
Time O(n): each day is pushed once and popped at most once, so the inner loop runs at most n times in all. Memory O(n) for the stack and the answer.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗