daily_temperatures
1# @leet start 2class Solution: 3 def dailyTemperatures(self, temperatures: list[int]) -> list[int]: 4 """ 5 This problem asks to find the next greater item in the list and 6 return said distance for every item. 7 8 The naive way of doing it is in $O(n^2)$ time. For each temperature, 9 we run a for loop until we find the next greater temperature, and set it 10 in the current index. 11 12 There's an $O(n)$ solution that involves using a stack. 13 We start off with an empty stack. 14 For every temperature we encounter, we check the stack in reverse. 15 If the current temperature is greater than the previous temperature, we 16 pop it and set its day's value to the distance between our element and 17 the previous element. 18 19 We do this in a while loop to make sure that all temperatures that haven't 20 found a higher temperature yet are taken care of. 21 When we encounter a temperature higher than our current temperature, 22 we add our current temperature to the stack, and wait for the next iteration. 23 24 All items left on the stack have their days set to 0, and the array is returned. 25 """ 26 days = [0 for _ in range(len(temperatures))] 27 28 stack = [] 29 for i, temp in enumerate(temperatures): 30 while stack and temp > stack[-1][0]: 31 prev_index = stack[-1][1] 32 days[prev_index] = i - prev_index 33 stack.pop() 34 stack.append((temp, i)) 35 return days 36 37 38# @leet end 39sol = Solution() 40 41 42def test(): 43 assert sol.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [ 44 1, 45 1, 46 4, 47 2, 48 1, 49 1, 50 0, 51 0, 52 ]
class
Solution:
3class Solution: 4 def dailyTemperatures(self, temperatures: list[int]) -> list[int]: 5 """ 6 This problem asks to find the next greater item in the list and 7 return said distance for every item. 8 9 The naive way of doing it is in $O(n^2)$ time. For each temperature, 10 we run a for loop until we find the next greater temperature, and set it 11 in the current index. 12 13 There's an $O(n)$ solution that involves using a stack. 14 We start off with an empty stack. 15 For every temperature we encounter, we check the stack in reverse. 16 If the current temperature is greater than the previous temperature, we 17 pop it and set its day's value to the distance between our element and 18 the previous element. 19 20 We do this in a while loop to make sure that all temperatures that haven't 21 found a higher temperature yet are taken care of. 22 When we encounter a temperature higher than our current temperature, 23 we add our current temperature to the stack, and wait for the next iteration. 24 25 All items left on the stack have their days set to 0, and the array is returned. 26 """ 27 days = [0 for _ in range(len(temperatures))] 28 29 stack = [] 30 for i, temp in enumerate(temperatures): 31 while stack and temp > stack[-1][0]: 32 prev_index = stack[-1][1] 33 days[prev_index] = i - prev_index 34 stack.pop() 35 stack.append((temp, i)) 36 return days
def
dailyTemperatures(self, temperatures: list[int]) -> list[int]:
4 def dailyTemperatures(self, temperatures: list[int]) -> list[int]: 5 """ 6 This problem asks to find the next greater item in the list and 7 return said distance for every item. 8 9 The naive way of doing it is in $O(n^2)$ time. For each temperature, 10 we run a for loop until we find the next greater temperature, and set it 11 in the current index. 12 13 There's an $O(n)$ solution that involves using a stack. 14 We start off with an empty stack. 15 For every temperature we encounter, we check the stack in reverse. 16 If the current temperature is greater than the previous temperature, we 17 pop it and set its day's value to the distance between our element and 18 the previous element. 19 20 We do this in a while loop to make sure that all temperatures that haven't 21 found a higher temperature yet are taken care of. 22 When we encounter a temperature higher than our current temperature, 23 we add our current temperature to the stack, and wait for the next iteration. 24 25 All items left on the stack have their days set to 0, and the array is returned. 26 """ 27 days = [0 for _ in range(len(temperatures))] 28 29 stack = [] 30 for i, temp in enumerate(temperatures): 31 while stack and temp > stack[-1][0]: 32 prev_index = stack[-1][1] 33 days[prev_index] = i - prev_index 34 stack.pop() 35 stack.append((temp, i)) 36 return days
This problem asks to find the next greater item in the list and return said distance for every item.
The naive way of doing it is in $O(n^2)$ time. For each temperature, we run a for loop until we find the next greater temperature, and set it in the current index.
There's an $O(n)$ solution that involves using a stack. We start off with an empty stack. For every temperature we encounter, we check the stack in reverse. If the current temperature is greater than the previous temperature, we pop it and set its day's value to the distance between our element and the previous element.
We do this in a while loop to make sure that all temperatures that haven't found a higher temperature yet are taken care of. When we encounter a temperature higher than our current temperature, we add our current temperature to the stack, and wait for the next iteration.
All items left on the stack have their days set to 0, and the array is returned.
sol =
<Solution object>
def
test():