## Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

## Solutions

### 1. Brute Force

TLE.

# Time: O(n^2)
# Space: O(1)
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
n = len(T)
res = []
for i in range(n-1):
gap = 0
for j in range(i+1, n):
if T[i] < T[j]:
gap = j - i
break
res.append(gap)
res.append(0)
return res

# Time Limit Exceeded
# 28/37 cases passed (N/A)


### 2. Stack

# Time: O(n)
# Space: O(n)
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
n = len(T)
stack = []
res = [0] * n
for i in range(n):
while stack and T[i] > T[stack[-1]]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return res

# 37/37 cases passed (492 ms)
# Your runtime beats 76.4 % of python3 submissions
# Your memory usage beats 55.26 % of python3 submissions (16.7 MB)