739. Daily Temperatures
## description
## 739. Daily Temperatures
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:
1Input: temperatures = [73,74,75,71,69,72,76,73]
2Output: [1,1,4,2,1,1,0,0]Example 2:
1Input: temperatures = [30,40,50,60]
2Output: [1,1,1,0]Example 3:
1Input: temperatures = [30,60,90]
2Output: [1,1,0]- –1 <= temperatures.length <= 105
- –30 <= temperatures[i] <= 100
Constraints:
## notes
### Intuition
A monotonic decreasing stack holds temperatures waiting for a warmer day. When a warmer temperature arrives, all cooler temperatures on the stack have found their answer.
### Implementation
Initialize the result array with zeros (default for days with no warmer future day). Use a stack storing (temperature, index) pairs. For each day, while the stack isn't empty and the current temperature is greater than the stack's top, pop and calculate the distance (current_index - popped_index). Store this in the result at the popped index. Push the current temperature and index.
### Edge-cases
Days that never see a warmer temperature remain 0 in the result (they're never popped from the stack).
- –Time: O(n) — each element pushed and popped at most once
- –Space: O(n) — stack in worst case (monotonically decreasing input)
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
5 n = len(temperatures)
6 result = [0] * n
7 # Space: O(n)
8 stack = []
9 # Time: O(n)
10 for i in range(n):
11 curr = temperatures[i]
12 while stack and stack[-1][0] < curr:
13 _, prev_i = stack.pop()
14 result[prev_i] = i - prev_i
15 stack.append((curr, i))
16 return result
17
18
19
20
21if __name__ == "__main__":
22 # Include one-off tests here or debugging logic that can be run by running this file
23 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
24 solution = Solution()
25