LeetCode 풀기 - 739. Daily Temperatures

739. Daily Temperatures

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

Daily Temperatures - LeetCode

문제)

솔루션1)

Brute-force로 접근해서 문제를 풀었더니 "Time Limit Exceeded"가 발생합니다.

 

시간 복잡도 : O(M^2)

공간 복잡도 : O(1)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        t = temperatures
        max_t = max(t)
        ret = []
        for i, t1 in enumerate(t):
            if t1 >= max_t:
                ret.append(0)
                continue
                
            for j in range(i+1, len(t)):
                if t1 < t[j]:
                    ret.append(j-i)
                    break
            else:
                ret.append(0)
        return ret

솔루션2)

monotonic stack(단조 스택)을 사용해서 시간 복잡도를 O(n)로 줄입니다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans = [0] * len(temperatures)
        q = deque()
        
        for idx, tmp in enumerate(temperatures):
            while q and temperatures[q[-1]] < tmp:
                ans[q[-1]] = idx - q[-1]
                q.pop()
            q.append(idx)
            
        return ans

 

참고:

https://labuladong.gitbook.io/algo-en/ii.-data-structure/monotonicstack

Special Data Structure: Monotonic Stack - algo-en