For each day, find how many days you must wait for a warmer temperature. If no warmer day comes, the answer for that day is 0.
DSA Animator › DSA Revision › Stack › Daily Temperatures
Remember: "next greater element" questions use a monotonic stack. Waiting items sit on the stack until something bigger resolves them. The video solves Daily Temperatures (LeetCode 739, Medium) with the Monotonic Stack pattern from the Stack topic, and you can replay every step in the interactive Daily Temperatures animation.
For each day, find how many days you must wait for a warmer temperature. If no warmer day comes, the answer for that day is 0.
For 73, 74, 75, 71, 69, 72, 76, 73, the answer is 1, 1, 4, 2, 1, 1, 0, 0. For example, after 75, the next warmer day is 76, four days later.
For each day, scanning forward for a warmer day is O of n squared. We want each day handled once.
Keep a stack of days that are still waiting for a warmer day. Their temperatures on the stack decrease from bottom to top. When a warmer day arrives, pop every colder day from the top, and their wait is the difference in days. Then push the current day.
Day 0, 73: push it. Day 1, 74 is warmer: day 0 waits 1, then push day 1. Day 2, 75 resolves day 1 with a wait of 1, then push. Days 3 and 4, 71 and 69, are colder, so they are pushed and wait. Day 5, 72 resolves day 4 with a wait of 1, and day 3 with a wait of 2. Day 6, 76 resolves day 5 with 1, and day 2 with 4. Day 7, 73 is pushed, and days 6 and 7 never see a warmer day, so they stay 0. The answer is 1, 1, 4, 2, 1, 1, 0, 0.
In code, keep a stack of indexes. For each day, while the top day is colder, pop it, and set its answer to today minus that day. Then push today. Every day is pushed and popped once, so it's O of n time and O of n space.
Remember: "next greater element" questions use a monotonic stack. Waiting items sit on the stack until something bigger resolves them.