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

739. Daily Temperatures

문제 링크

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

문제 설명

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

제한 사항

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

입출력 예 #1

1. Input: temperatures = [73,74,75,71,69,72,76,73]
2. Output: [1,1,4,2,1,1,0,0]

입출력 예 #2

1. Input: temperatures = [30,40,50,60]
2. Output: [1,1,1,0]

입출력 예 #3

1. Input: temperatures = [30,60,90]
2. Output: [1,1,0]

문제 풀이

stack을 이용하여 각 온도의 idx값을 저장하고, 현재 온도가 이전 온도보다 높다면 stack에서 하나씩 pop하여 현재 idx - pop_idx를 한 결과를 리스트에 삽입한다.

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