[스택, 큐] 일일 온도

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

 

 

작성 코드

 

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = []
        for idx1, value in enumerate(temperatures):            
            isExist = 0
            for idx2, com in enumerate(temperatures[idx1 + 1:]):
                print(com, value)
                if com > value :
                    isExist = 1
                    break
            print(isExist)
            answer.append(idx2 + isExist)
        return answer

 

• stack 을 이용한 건 X
• 시간 복잡도가 O(N^2)
• temperatures = [55,38,53,81,61,93,97,32,43,78] TestCase 에 대한 오류

 

 

이상 코드

 

from typing import List


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        answer = [0] * len(T)
        stack = []
        for i, cur in enumerate(T):
            # 현재 온도가 스택 값보다 높다면 정답 처리
            while stack and cur > T[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)

        return answer

 

• 처리되지 못한 인덱스 저장