Initial Solution
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = []
visited = [0] * len(temperatures)
stack:List[tuple] = [] # (temperature, index)
for i, t in enumerate(temperatures):
while stack and t > stack[-1][0] :
visited[stack[-1][1]] = i - stack[-1][1]
stack.pop()
stack.append((t, i))
return visited
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n) where n is the length of the temperatures array. Each element is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack in the worst case (when temperatures are in descending order) and O(n) for the visited array.