스택 [리트코드] 739. Daily Temperatures

초기작성

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = []
        for i in range(len(temperatures)):
            appended = False
            for j in range(i, len(temperatures)):
                if temperatures[j] > temperatures[i]:
                    result.append(j-i)
                    appended = True
                    break
            if not appended:
                result.append(0)

        return result


print(Solution.dailyTemperatures(Solution(),
                                 [30, 60, 90]))

이중for 문으로 인덱스를 접근하니 n^2의 시간복잡도가 들어 시간초과가 나는 듯 하다.

스택을 이용하여 각 인덱스를 담고, 들어오는 인덱스의 값을 비교하여 자신보다 높은 값이 들어오면 인덱스를 pop

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []
        for index, val in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < val:
                last = stack.pop()
                res[last] = index-last
            stack.append(index)
        return res

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []
        for index, val in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < val:
                res[stack[-1]] = index-stack[-1]
                stack.pop()
            stack.append(index)
        return res


print(Solution.dailyTemperatures(Solution(),
                                 [30, 40, 50, 60]))

참고로 이렇게 수정했을 때는 시간초과가 일어났는데 stack[-1]에 접근하는 것으로 시간복잡도가 꽤 많이 올라가는듯?