Leetcode Link

A brute-force solution would use two nested loops to compare each day’s temperature with the upcoming days, resulting in O(n²) time complexity, which is inefficient for large inputs.

To optimize this, we can use a monotonic stack to store temperature information, reducing the time complexity to O(n).

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

Step-by-step Stack Simulation:
We first initialize a result array of the same length, filled with 0s:

res = [0, 0, 0, 0, 0, 0, 0, 0]  
stack = []  // Each element is [index, temperature]

  • Index = 0
    Stack: [[0, 73]]
    We push the current day.

  • Index = 1
    74 > 73 → pop [0, 73]
    res[0] = 1 - 0 = 1
    Stack: [[1, 74]]
    Since today is warmer than the day at the top of the stack, we resolve the waiting day (index 0).
    Then, we push the current day.

  • Index = 2
    75 > 74 → pop [1, 74]
    res[1] = 2 - 1 = 1
    Stack: [[2, 75]]
    Again, today is warmer than the top of the stack, so we resolve index 1.
    Push current index to wait for a warmer day.

  • Index = 3
    71 < 75 → push [3, 71]
    Stack: [[2, 75], [3, 71]]
    Since today is cooler, we can’t resolve any previous day.
    Just push this day onto the stack.

  • Index = 4
    69 < 71 → push [4, 69]
    Stack: [[2, 75], [3, 71], [4, 69]]
    Still cooler than any unresolved day, so we just push.

  • Index = 5

    72 > 69 → pop [4, 69], res[4] = 5 - 4 = 1

    72 > 71 → pop [3, 71], res[3] = 5 - 3 = 2

    72 < 75 → push [5, 72]

    Stack: [[2, 75], [5, 72]]

… and so on, until the entire array is processed.

This approach ensures that each temperature is pushed and popped from the stack at most once, resulting in an efficient O(n) solution.

This is JAVA version

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<int[]> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            int t = temperatures[i];
            while (!stack.isEmpty() && t > stack.peek()[1]) {
                int[] top = stack.pop();
                res[top[0]] = i - top[0];
            }
            stack.push(new int[]{i, t});
        }
        return res;
    }
}