[리트코드] 739. Daily Temperatures

문제 링크

https://leetcode.com/problems/daily-temperatures/description/

느낀 점

어떻게든 O(N^2)이 안되는 방법을 생각해내야하는데, 지금까지 가장 큰 시점보다 더 올라간 시점을 찾았을 때, 이전에 이 점 보다 더 작은 점들을 계산해주는 방식으로 구했음. 솔직히 처음 문제를 보고 이렇게 딱 생각하기는 쉽지 않을 것 같다..

from typing import List
import collections
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        count = [0 for _ in range(len(T))] 
        stack = [] 
        T = collections.deque(T) 
        for ind, item in enumerate(T) :
            while stack and T[stack[-1]] < item :  
                last = stack.pop()
                count[last] = ind - last
            stack.append(ind)
        return count