833. How Long Until It Gets Warmer

A weather station recorded one temperature per day for n days.

For each day, print HOW MANY DAYS you would have to wait for a strictly warmer reading. If no later day is warmer, print 0 for that day.

Print all n answers on one line, separated by single spaces.

73 74 75 71 69 72 76 73 -> 1 1 4 2 1 1 0 0 30 40 50 60 -> 1 1 1 0 5 5 5 5 5 -> 0 0 0 0 0

Day 2 reads 75, and the next reading above 75 is the 76 on day 6, four days later. The last row is flat, and equal is not warmer, so nothing ever gets an answer.

## Why this is not just problem 154 again

Problem 154 prints the next larger VALUE. This prints the DISTANCE to it. The scan is the same but what you record when a pop happens is different, and the distance version is the one the rest of this topic actually needs: widths, spans and stretch lengths are all distances, never values.

That also changes which thing goes on the stack. To report a value you can push values; to report a distance you must push INDICES, because the answer is i - j and you need j.

## Why scanning forward from every day is too slow

The obvious program walks forward from each day until it meets something warmer. On a row that only cools, 100 99 98 ... , every day scans to the end and finds nothing, which is about n^2 / 2 comparisons. At n = 200000 that is 2 * 10^10.

## The stack, and why it decreases

Hold a stack of days that are still waiting. When day i arrives, every waiting day whose reading is strictly below t[i] has just been answered, so pop it and record i - j.

The survivors sit in non-increasing order of temperature from the bottom up, because anything smaller than the top would have been popped on arrival. Decreasing is right here because the question asks for the next BIGGER value; the increasing stack answers the opposite question.

## What is left at the end

Whatever is still waiting never found a warmer day. Those days answer 0. Initialise the whole answer array to 0 before the scan and the leftovers take care of themselves.

## The comparison that decides the flat case

Pop on t[top] < t[i], strictly. Loosen it to <= and an equal reading counts as warmer, so 5 5 5 5 5 would answer 1 1 1 1 0 instead of all zeros. The word in the statement is "strictly warmer", so the test is strict.

## Related problems

Problem 154 is the same scan reporting the value instead of the gap, and problem 157 counts how far BACK the current day dominates rather than how far forward it waits.

## Sizes and widths

Readings reach 10^9 in absolute size, but every answer is a DISTANCE, at most n. Nothing is summed and nothing is multiplied, so 32 bits holds the whole computation.

## Cost

Time O(n): each day is pushed once and popped at most once. Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ t[i] ≤ 10^9`