739. Daily Temperatures

• python3

Problem

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

Plan Solution

1. 답변을 넣을 리스트 생성 : 리스트 길이는 주어진 온도 리스트 길이
2. 스택 생성
3. 온도 리스트에서 반복문
   1. stack에서 값이 있고 온도 리스트에서 그 스택의 제일 윗값에 해당하는 온도가 현재 온도보다 낮을 경우에 스택에서 팝.
   2. 스택에서 팝한 값에서 현재 인덱스 값을 빼면 그 인덱스 날로부터 현재까지 길이 = 온도가 올라가는 날
   3. 현재 인덱스 스택에 넣기
4. 답변 반환

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # temperature 길이만큼 list 생성
        answer = [0] * len(temperatures)
        # 인덱스 값을 넣을 stack 생성
        stack = []

        # temperatures에서 인덱스와 각 값을 가져오기
        for i, temp in enumerate(temperatures):
            # stack에 값이 있고 
            # temperature에서 그 인덱스 값에 해당하는 온도가 현재 온도보다 낮을 경우
            while stack and temperatures[stack[-1]] < temp:
                index = stack.pop()
                answer[index] = i - index
            stack.append(i)
        
        return answer

example

입력 배열: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

1. i = 0, t = 73:

   스택: [0]
   answer: [0, 0, 0, 0, 0, 0, 0, 0]

2. i = 1, t = 74:

   현재 온도 74가 스택의 마지막 인덱스 0의 온도 73보다 높습니다.
   answer[0] = 1 - 0 = 1
   스택: [] (값이 팝됨)
   스택: [1] (현재 인덱스 추가)
   answer: [1, 0, 0, 0, 0, 0, 0, 0]

3. i = 2, t = 75:
   현재 온도 75가 스택의 마지막 인덱스 1의 온도 74보다 높습니다.
   answer[1] = 2 - 1 = 1
   스택: [] (값이 팝됨)
   스택: [2] (현재 인덱스 추가)
   answer: [1, 1, 0, 0, 0, 0, 0, 0]

4. i = 3, t = 71:
   현재 온도 71가 스택의 마지막 인덱스 2의 온도 75보다 낮습니다.
   스택: [2, 3] (현재 인덱스 추가)
   answer: [1, 1, 0, 0, 0, 0, 0, 0]

5. i = 4, t = 69:
   현재 온도 69가 스택의 마지막 인덱스 3의 온도 71보다 낮습니다.
   스택: [2, 3, 4] (현재 인덱스 추가)
   answer: [1, 1, 0, 0, 0, 0, 0, 0]

6. i = 5, t = 72:

   현재 온도 72가 스택의 마지막 인덱스 4의 온도 69보다 높습니다.
   answer[4] = 5 - 4 = 1
   스택: [2, 3] (값이 팝됨)
   현재 온도 72가 스택의 마지막 인덱스 3의 온도 71보다 높습니다.
   answer[3] = 5 - 3 = 2
   스택: [2] (값이 팝됨)
   스택: [2, 5] (현재 인덱스 추가)
   answer: [1, 1, 0, 2, 1, 0, 0, 0]

7. i = 6, t = 76:

   현재 온도 76가 스택의 마지막 인덱스 5의 온도 72보다 높습니다.
   answer[5] = 6 - 5 = 1
   스택: [2] (값이 팝됨)
   현재 온도 76가 스택의 마지막 인덱스 2의 온도 75보다 높습니다.
   answer[2] = 6 - 2 = 4
   스택: [] (값이 팝됨)
   스택: [6] (현재 인덱스 추가)
   answer: [1, 1, 4, 2, 1, 1, 0, 0]

8. i = 7, t = 73:

   현재 온도 73가 스택의 마지막 인덱스 6의 온도 76보다 낮습니다.
   스택: [6, 7] (현재 인덱스 추가)
   answer: [1, 1, 4, 2, 1, 1, 0, 0]

9. 최종 결과
   answer: [1, 1, 4, 2, 1, 1, 0, 0]

Result

• Time Complextiy : O(n)
• Space Complexity : O(n)