Loading...
Loading...
Loading...
Priya is planning a trip during her semester break and logged the temperature of her city for n days. For each day she wants to know how many days she must wait to get a strictly warmer day.
For day i, print the smallest number of days d such that the temperature on day i + d is higher than on day i. If no later day is warmer, print 0 for that day.
Example
Input
8 31 30 33 29 28 32 35 30
Output
2 1 4 2 1 1 0 0
Day 1 (31) waits 2 days for 33. Day 4 (29) waits 2 days for 32. Day 7 (35) and day 8 (30) have no warmer day later, so they get 0.
Try the problem first. Open one hint at a time.
Checking every later day for every day works, but with 10^5 equal days it does about 5 × 10^9 comparisons.
Keep a stack of the days that are still waiting for a warmer day. Store the day number, not the temperature.
When a new day is warmer than the day on top of the stack, that waiting day has found its answer. Pop it and repeat.
The days left on the stack at the end never found a warmer day, so their answer stays 0.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor