Daily Temperatures

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

Daily Temperatures - LeetCode

class Solution:
    def dailyTemperatures(self, temperatures):
        stack = []
        result = [0] * len(temperatures)
        for i in range(len(temperatures)):
            tmp = temperatures[i]
            while stack:
                if tmp > stack[-1][0]:
                    result[stack[-1][1] - 1] = i + 1 - stack[-1][1]
                    stack.pop()
                elif tmp <= stack[-1][0]:
                    break
            stack.append((temperatures[i], i + 1))
        return result

 

• 처음에는 stack 자료구조를 도입해 풀 생각을 못했었고, O(n * n)의 시간복잡도를 가진 풀이를 생각해냈다.
• 하지만 조건에 걸리므로
• stack 자료구조에 튜플로 온도를 넣어주고, 특정 조건이 계속 변화하면서 한정적으로 stack 안의 원소에 영향을 끼치는 방법을 이용하여 풀이하였다.