Skip to main content

739. Daily Temperatures

Python​

First Try: Liter days (Time Limit Exceeded)​

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        answer = [0] * len(T)
        len_t = len(T)

        for index, t in enumerate(T):
            futures = T[index+1:]

            for future_t in futures:
                answer[index] += 1
                if future_t > t:
                    break
            else:
                answer[index] = 0

        return answer

Second Try: Liter possible tempatures (Time Limit Exceeded)​

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        temps_map = defaultdict(list)
        answer = []

        for day, temp in enumerate(T):
            temps_map[temp].append(day)

        for day, temp in enumerate(T):
            larger_future_temp_days = []
            for temp_key in [key for key in temps_map.keys() if key > temp]:
                larger_future_temp_days += [future_day for future_day in temps_map[temp_key] if future_day > day]

            answer.append(min(larger_future_temp_days)-day if larger_future_temp_days else 0)

        return answer

Third time: Use stack to store only the days which matters (Pass)​

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        N = len(T)
        answer = [0] * N
        for day in range(N):
            while stack and stack[-1][1] < T[day]:
                key, val = stack.pop()
                answer[key] = day - key
            stack.append((day, T[day]))
        return answer