Daily Temperatures
Given a list of daily temperatures, produce an array where each entry is the number of days you must wait after that day until a strictly warmer temperature occurs, or 0 if it never does.
- 1 ≤ n ≤ 10^5
- 30 ≤ temperatures[i] ≤ 100
- "Next greater element" for each position
- Indices waiting for an answer form a decreasing sequence of values
- Each index is pushed and popped at most once
Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.
Scan left to right with a stack of indices whose temperatures are strictly decreasing from bottom to top. For the current day, pop every index with a lower temperature — the current day is their next warmer day, so record the distance. Then push the current index. Days left on the stack at the end never get a warmer day and keep the default 0.
- Brute force scanning ahead is O(n^2). Scanning right to left with jumps through the answer array also achieves O(n) with O(1) extra space.