Hints — p51 Daily Temperatures

Hint 1. Brute force is “for each i, scan right until you find a warmer day.” O(n²) on 10^5 input → TLE. You need O(n).

Hint 2. Reframe: think of each not-yet-resolved day as waiting for warmer weather. When a new day arrives, who on the waiting list just got their answer?

Hint 3. The waiting list, by construction, has STRICTLY DECREASING temperatures (anyone with a lower temp than someone earlier on the list would have already been resolved when that earlier person joined). This is your monotonic stack.

Hint 4. Store indices, not values — you need i - j to compute “days waited.” Read values via T[stack[-1]].

Hint 5. Each index is pushed and popped at most once → amortized O(n). Be ready to defend this argument: the inner while loop’s total work across the outer loop is bounded by total pops ≤ n.

If still stuck: see solution.py.