739. Daily Temperatures (Array, Stack, Monotonic Stack)

링크 - https://leetcode.com/problems/daily-temperatures/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

우리는 Stack을 사용하여 이 문제를 풀 수 있다. 먼저 stack에 값이 있는 지 확인 후, stack의 peak의 온도가 현재 온도보다 낮으면 계속 pop을 해서 pop한 index의 값에 현재 index와의 diff를 집어넣는다.

 

혹은 우리가 space complexity를 O(1)로 하고 싶다면 오른쪽에서 왼쪽으로 이동하면서 문제를 풀어도 된다.

1. 오른쪽에서 왼쪽으로 이동하면서 현재 temperature값을 확인한다. 현재 temperature이 가장 뜨거운 거라면, hottest값을 현재 temperature로 갱신하고 왼쪽으로 이동한다.

2. 만약 현재 temperature가 가장 뜨거운게 아니라면, 우리는 오른쪽에 현재 temperature보다 더 높은 값을 가지는 temperature가 있음을 알 수 있다. 따라서 현재 날로부터 일단 하루 오른쪽으로 이동하여 그날 temperature이 현재 temperature보다 높은지 확인한다. 현재 temperature가 더 높다면 우리가 이미 ans에 넣어놓은 값을 이동하여 그 day만큼 다시 이동하여 temperature을 비교한다.

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(temperatures)

        for i, t in enumerate(temperatures):
            while stack and stack[-1][0] < t:
                prev_t, prev_i = stack.pop()
                ans[prev_i] = i - prev_i
            stack.append((t, i))

        return ans
        
# O(1) Space Complexity
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        hottest = 0
        ans = [0] * n

        for curr_day in range(n-1, -1, -1):
            curr_temp = temperatures[curr_day]
            if curr_temp >= hottest:
                hottest = curr_temp
                continue

            days = 1
            while temperatures[curr_day + days] <= curr_temp:
                days += ans[curr_day + days]
            ans[curr_day] = days

        return ans

Complexity

Time Complexity: O(N) 

Space Complexity: O(N) - stack, O(1) - from right to left approach