[LeetCode/리트코드]#739:Daily Temperatures [파이썬/python/배열/array]

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

온도 list를 받으면 각 날에 대해 - 현재날짜보다 다음날짜가 따뜻한 날짜의 개수(number of days)를 구하는 것이다.

브루트포스 문제로 완전탐색을 하면된다. 

각 온도의 날짜를 모두 돌면 O(N^2)의 시간복잡도다.

비효율적인 완전탐색보다 좀 더 빠르게 짤 수 없을까?

 

배열을 사용하여 구현해보자.

N(온도길이)만큼 iterate하면 시간복잡도는 O(N)이다. 

공간복잡도 또한 O(N)이다. 

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        n=len(temperatures)
        ans = [0]*n
        stack=[]
        
        for cur_day, cur_temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < cur_temp:
                prev_day = stack.pop()
                ans[prev_day] = cur_day - prev_day
                
            stack.append(cur_day)
            
        return ans