Daily Temperatures
Problem Description
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 ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
- 1 <= temperatures.length <= 105
- 30 <= temperatures[i] <= 100
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
We can start with a straightforward approach by simply checking each temperature against all the following temperatures to see when a warmer day occurs. This involves traversing every pair of days, which can be inefficient.
Steps:
- For each day in the list of temperatures, we need to find the number of days until a warmer temperature appears.
- We'll make a nested iteration, fixing one element from the start and iterating through the following temperatures to find the first one greater than our fixed element.
- If we find such a day, we calculate how many days ahead it is and store that in our result list.
Code:
- Time Complexity: O(n^2) due to nested for loops.
- Space Complexity: O(1), aside from the output array.
2. Using a Stack
Intuition:
By utilizing a stack, we can reduce the repeated comparisons to gain an optimal solution. We will use a stack to keep track of indices of the temperatures that need to find a warmer temperature.
Steps:
- We will maintain a stack to store indices of the temperatures.
- As we iterate over each day's temperature, we compare it with the temperatures corresponding to the indices in our stack.
- If the current day's temperature is warmer than the temperature at the index stored at the top of the stack, we pop the index from the stack and update our result with the number of days we've moved forward to find a warmer temperature.
- We push the current index onto the stack if we don't find a warmer temperature.
- This way, each temperature is processed once, ensuring efficiency.
Code:
- Time Complexity: O(n), each element is pushed and popped at most once.
- Space Complexity: O(n), due to the stack storing up to n indices.