Daily Temperatures

Given a list of daily temperatures, return an array where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future day, put 0.

Function signature

func DailyTemperatures(temperatures []int) []int

Inputs / outputs

• temperatures: slice of integers.
• Return: slice of wait times.

Example

temperatures = [73,74,75,71,69,72,76,73]
Output = [1,1,4,2,1,1,0,0]

Constraints

• 1 <= len(temperatures) <= 100_000
• -100 <= temperatures[i] <= 200

Core idea (near-solution)

Use a monotonic decreasing stack of indices. When a new temperature is higher than the top, you have found the next warmer day for that index.

Invariant: temperatures at indices in the stack are strictly decreasing from bottom to top.

Algorithm (step-by-step)

1. Initialize an output array with zeros.
2. Initialize an empty stack of indices.
3. For each index i:
   • While stack not empty and temperatures[i] > temperatures[stackTop]:
     • Pop j and set answer[j] = i - j.
   • Push i onto the stack.
4. Return answer.

Correctness sketch

• Invariant: temperatures at indices in the stack are strictly decreasing from bottom to top.
• The stack remains monotonic, so each element’s next boundary is discovered when it is popped.
• Each index is pushed and popped at most once, and its answer is finalized then.
• Therefore all outputs computed on pop are correct.

Trace (hand walkthrough)

Example input:
temperatures = [73,74,75,71,69,72,76,73]
Output = [1,1,4,2,1,1,0,0]

Walk:
- i=0 (73) push[0]; i=1 (74) >73 -> ans[0]=1, push[1]
- i=2 (75) >74 -> ans[1]=1, push[2]
- i=3 (71) push[3]; i=4 (69) push[4]
- i=5 (72) >69 -> ans[4]=1; >71 -> ans[3]=2; push[5]
- i=6 (76) >72 -> ans[5]=1; >75 -> ans[2]=4; push[6]

Pitfalls to avoid

• Storing temperatures instead of indices (you need distance).
• Using a non-strict monotonic condition.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Use a stack of indices with decreasing temperatures.
• When current temp is higher, pop and compute distances.