LeetCode #739 Daily Temperatures Solution & Explanation

LeetCode Problem

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

💡Hint 1

If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, …, 99, or 100. We could remember when all of them occur next.

Solution

Upon encountering this question, my initial instinct was undoubtedly to employ a two-for-loop approach. However, I promptly dismissed it, as an O(n²) time complexity is unequivocally not an optimal solution.

Indeed, for this question, there is a straightforward solution involving the use of a stack. We leverage its Last-In-First-Out (LIFO) property to efficiently address the problem at hand.

C# Solution

Solution1

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        Stack<int> stack = new Stack<int>();
        int[]res = new int[temperatures.Length];

        for(var i=0; i<temperatures.Length; i++){
            while(stack.Count != 0 &&temperatures[i] > temperatures[stack.Peek()]){
                var top = stack.Pop();
                res[top] = i-top;
            }
            stack.Push(i);
        }
        return res;
    }
}

We use a stack to represent a decreasing stack of temperature indices, where the higher temperatures are at the bottom.

When encountering a temperature greater than the one at the top of the stack, we enter a while loop to continue checking until the temperature is not higher than the top of the stack or the stack is empty.

Conclusion

Upon encountering this question, it reminds me of the recent weather changes in Taiwan over the past few weeks, which have been extremely significant.

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Daily Temperatures – LeetCode

Some Random LeetCode posts