Daily temperatures

For each day, find how many days until a warmer one, using a monotonic stack of days still waiting for an answer.

The idea

The stack holds days whose warmer day has not been found yet, with temperatures decreasing from bottom to top. When a warmer day arrives, it is the answer for every cooler day still waiting on top of the stack.

Code

public static int[] DailyTemperatures(int[] temps) {
    var result = new int[temps.Length];
    var stack = new Stack<int>(); // indices waiting for a warmer day
    for (int i = 0; i < temps.Length; i++) {
        while (stack.Count > 0 && temps[stack.Peek()] < temps[i]) {
            int j = stack.Pop();
            result[j] = i - j;
        }
        stack.Push(i);
    }
    return result;
}

Tips

• Store day indices on the stack, not temperatures, so the gap i - j can be recorded once the answer is known.
• This is the same monotonic-stack shape as next greater element, just recording a distance instead of a value.

In the .NET library

Every index is pushed once and popped at most once, so the while loop total work across the whole run is still O(n), even though it looks nested.