[LeetCode 75] Medium - 739. Daily Temperatures

739. Daily Temperatures

 

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 <= 10^5
• 30 <= temperatures[i] <= 100

 

문제 해설

 

이 문제는 Daily Temperatures(일일 온도) 문제로, 주어진 배열 temperatures에서 각 날짜 이후 더 따뜻한 날이 오기까지 걸리는 날 수를 계산하는 것입니다. 만약 더 따뜻한 날이 없으면 해당 위치의 결과값은 0이 됩니다.

---

문제 세부 설명

1. 입력:
   • temperatures: 정수 배열로, 각 원소는 특정 날의 온도를 나타냅니다.
   • 예: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
2. 출력:
   • answer: 정수 배열로, answer[i]는 temperatures[i] 이후 더 따뜻한 날이 오기까지 걸리는 날 수를 나타냅니다.
   • 만약 더 따뜻한 날이 없다면, answer[i] = 0.
3. 제약 조건:
   • 배열 길이: 1 ≤ temperatures.length ≤ 10^5
   • 온도 범위: 30 ≤ temperatures[i] ≤ 100

문제 풀이 방법

이 문제는 **Monotonic Stack(단조 스택)**을 사용하여 해결할 수 있습니다. 배열을 뒤에서부터 순회하면서 더 따뜻한 날을 찾아가는 방식으로 문제를 풉니다. 아래는 문제를 해결하기 위한 상세한 접근 방식과 코드입니다.

---

해결 방법

1. 단조 감소 스택(Monotonic Decreasing Stack):
   • 스택에 날짜의 인덱스를 저장하며, 해당 인덱스의 온도는 스택 아래에서 위로 점점 작아지는 순서를 유지합니다.
   • 새로운 온도가 더 높아지면 스택에서 값을 제거하면서, 더 따뜻한 날을 계산합니다.
2. 구현 순서:
   1. 온도 배열을 뒤에서 앞으로 순회합니다.
   2. 현재 온도보다 높은 온도가 나올 때까지 스택에서 값을 제거합니다.
   3. 스택의 맨 위에는 현재 온도보다 높은 "다음 더 따뜻한 날의 인덱스"가 있습니다.
      • 이 인덱스를 이용해 몇 일 후 더 따뜻한 날이 오는지 계산합니다.
   4. 현재 날짜를 스택에 추가하여 이후 날짜를 처리할 때 참고합니다.
3. 시간 복잡도:
   • 배열을 한 번 순회하면서 값을 추가하거나 제거하므로 O(n).
   • 스택의 각 원소는 한 번만 삽입되고 한 번만 제거됩니다.

def dailyTemperatures(temperatures):
    # Step 1: 변수 초기화
    n = len(temperatures)  # 온도 배열의 길이
    answer = [0] * n  # 결과 배열, 초기값은 모두 0
    stack = []  # 단조 감소 스택: 온도가 높아질 때까지 기다릴 날의 인덱스 저장

    # Step 2: 배열을 뒤에서 앞으로 순회
    for i in range(n - 1, -1, -1):
        # 현재 온도보다 작거나 같은 값을 스택에서 제거
        while stack and temperatures[i] >= temperatures[stack[-1]]:
            stack.pop()
        
        # Step 3: 더 따뜻한 날 확인
        # 스택이 비어 있지 않으면 스택 맨 위는 더 따뜻한 날의 인덱스
        if stack:
            answer[i] = stack[-1] - i  # 더 따뜻한 날까지의 간격 계산
        
        # 현재 날짜를 스택에 추가
        stack.append(i)
    
    # 결과 반환
    return answer
    
"""
# 예제 시뮬레이션
# temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

# 초기 상태
# temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
# answer = [0, 0, 0, 0, 0, 0, 0, 0]
# stack = []

# 시뮬레이션 과정:
# Step 1: i = 7 (73°F)
# - 스택이 비어 있으므로 더 따뜻한 날 없음 → answer[7] = 0
# - stack = [7]

# Step 2: i = 6 (76°F)
# - 현재 온도(76°F)가 스택 맨 위의 온도(73°F)보다 높음 → 스택에서 제거
# - 스택이 비어 있으므로 더 따뜻한 날 없음 → answer[6] = 0
# - stack = [6]

# Step 3: i = 5 (72°F)
# - 현재 온도(72°F)가 스택 맨 위의 온도(76°F)보다 낮음 → 더 따뜻한 날은 6일째
# - answer[5] = 6 - 5 = 1
# - stack = [6, 5]

# Step 4: i = 4 (69°F)
# - 현재 온도(69°F)가 스택 맨 위의 온도(72°F)보다 낮음 → 더 따뜻한 날은 5일째
# - answer[4] = 5 - 4 = 1
# - stack = [6, 5, 4]

# Step 5: i = 3 (71°F)
# - 현재 온도(71°F)가 스택 맨 위의 온도(69°F)보다 높음 → 스택에서 제거
# - 현재 온도(71°F)가 스택 맨 위의 온도(72°F)보다 낮음 → 더 따뜻한 날은 5일째
# - answer[3] = 5 - 3 = 2
# - stack = [6, 5, 3]

# Step 6: i = 2 (75°F)
# - 현재 온도(75°F)가 스택 맨 위의 온도(71°F)보다 높음 → 스택에서 제거
# - 현재 온도(75°F)가 스택 맨 위의 온도(72°F)보다 높음 → 스택에서 제거
# - 현재 온도(75°F)가 스택 맨 위의 온도(76°F)보다 낮음 → 더 따뜻한 날은 6일째
# - answer[2] = 6 - 2 = 4
# - stack = [6, 2]

# Step 7: i = 1 (74°F)
# - 현재 온도(74°F)가 스택 맨 위의 온도(75°F)보다 낮음 → 더 따뜻한 날은 2일째
# - answer[1] = 2 - 1 = 1
# - stack = [6, 2, 1]

# Step 8: i = 0 (73°F)
# - 현재 온도(73°F)가 스택 맨 위의 온도(74°F)보다 낮음 → 더 따뜻한 날은 1일째
# - answer[0] = 1 - 0 = 1
# - stack = [6, 2, 1, 0]

# 최종 결과
# result = dailyTemperatures(temperatures)
# print(result)  # Output: [1, 1, 4, 2, 1, 1, 0, 0]
"""

 

 

• 배열을 뒤에서 앞으로 순회하며 단조 감소 스택을 사용해 각 날짜의 다음 더 따뜻한 날을 계산.
• 스택의 맨 위 값은 항상 현재보다 따뜻한 "가장 가까운 날"을 유지.

 

https://youtu.be/cTBiBSnjO3c?si=XZgFqDNhaDBxf8Ku

 

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # 결과 배열 초기화: 각 날짜에 대해 더 따뜻한 날까지 걸리는 일 수를 저장
        # 초기값은 모두 0 (더 따뜻한 날이 없는 경우, 기본값을 설정)
        res = [0] * len(temperatures)
        
        # 스택 초기화: [온도, 인덱스] 형태로 저장
        # 스택에는 "아직 더 따뜻한 날을 찾지 못한 날들"만 저장됨
        stack = []  # pair: [temp, index]

        # 모든 온도 순회
        for i, t in enumerate(temperatures):
        	# i: 현재 날짜의 인덱스., t: 현재 날짜의 온도.
            # 현재 온도 `t`가 스택 맨 위의 온도(stack[-1][0])보다 높은 경우
            # -> 더 따뜻한 날을 찾은 것 -> 따라서, 스택에서 값을 꺼내며 더 따뜻한 날을 계산
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()  # 스택에서 가장 위의 [온도, 인덱스] 제거
                res[stackInd] = i - stackInd  # 더 따뜻한 날까지 걸린 일 수 계산
            
            # 현재 온도와 인덱스를 스택에 추가
            # 이후 더 따뜻한 날을 찾기 위해 저장
            stack.append([t, i])
        
        # 결과 배열 반환
        return res

"""
# 순회 과정 기록
# 입력: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
#
# Day 0 (73°F):
# 스택 비어 있음 → 스택에 [73, 0] 추가
# stack = [[73, 0]]
#
# Day 1 (74°F):
# 74 > 73 → 스택에서 [73, 0] 제거
# res[0] = 1 - 0 = 1 (더 따뜻한 날까지 1일 걸림)
# 스택에 [74, 1] 추가
# res = [1, 0, 0, 0, 0, 0, 0, 0], stack = [[74, 1]]
#
# Day 2 (75°F):
# 75 > 74 → 스택에서 [74, 1] 제거
# res[1] = 2 - 1 = 1 (더 따뜻한 날까지 1일 걸림)
# 스택에 [75, 2] 추가
# res = [1, 1, 0, 0, 0, 0, 0, 0], stack = [[75, 2]]
#
# Day 3 (71°F):
# 71 <= 75 → 스택에 [71, 3] 추가
# stack = [[75, 2], [71, 3]]
#
# Day 4 (69°F):
# 69 <= 71 → 스택에 [69, 4] 추가
# stack = [[75, 2], [71, 3], [69, 4]]
#
# Day 5 (72°F):
# 72 > 69 → 스택에서 [69, 4] 제거
# res[4] = 5 - 4 = 1
# 72 > 71 → 스택에서 [71, 3] 제거
# res[3] = 5 - 3 = 2
# 스택에 [72, 5] 추가
# res = [1, 1, 0, 2, 1, 0, 0, 0], stack = [[75, 2], [72, 5]]
#
# Day 6 (76°F):
# 76 > 72 → 스택에서 [72, 5] 제거
# res[5] = 6 - 5 = 1
# 76 > 75 → 스택에서 [75, 2] 제거
# res[2] = 6 - 2 = 4
# 스택에 [76, 6] 추가
# res = [1, 1, 4, 2, 1, 1, 0, 0], stack = [[76, 6]]
#
# Day 7 (73°F):
# 73 <= 76 → 스택에 [73, 7] 추가
# stack = [[76, 6], [73, 7]]
#
# 최종 결과
# res = [1, 1, 4, 2, 1, 1, 0, 0]
"""

 

 

 

• 스택을 사용해 다음 더 따뜻한 날을 효율적으로 계산:
  • 현재 온도가 스택의 맨 위 온도보다 높으면 더 따뜻한 날을 찾은 것이므로 스택에서 제거하고 결과 배열을 업데이트.
  • 새로운 날의 정보를 스택에 추가.
• 시간 복잡도:
  • 각 온도가 스택에 한 번 추가되고 한 번 제거되므로 O(n).
• 공간 복잡도:
  • 스택에 최대 n개의 요소가 들어갈 수 있으므로 O(n).