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.
1. 문제 상황
문제를 간단히 다시 보기 : 오늘 온도가 더 따뜻해지려면 며칠을 기다려야 하는지
앞에서부터 풀면 모든 날에 대해 모든 이후 날들을 다 비교해야 하니까 매우 비효율적임
Brute Force는 O(n^2)이 된다.
2. 뒤에서부터 찾아보면 어떨까?
우리가 찾고 싶은 건 더 따뜻한 날이기 때문에 뒤에서 앞으로 살펴보면 이미 지나간 일을 기억할 필요가 없음.
왜냐하면 뒤에서부터 보면 미래 정보를 계속 update 할 수 있기 때문.
3. stack
스택은 항상 이전까지 확인한 온도들 중 가장 의미 있는 값들로만 남겨두기
def dailyTemperatures(temperatures):
n = len(temperatures) # 전체 날 수
answer = [0] * n # 결과를 저장할 리스트
stack = [] # 스택 (인덱스를 저장)
# 뒤에서 앞으로 순회
for i in range(n - 1, -1, -1): # i: 현재 날의 인덱스
# 현재 온도보다 낮거나 같은 온도는 스택에서 제거
# 이렇게 하면 스택의 맨 위는 항상 가장 가까운 더 높은 온도의 가진 날의 인덱스를 갖게 됨
while stack and temperatures[stack[-1]] <= temperatures[i]:
stack.pop()
# 스택이 비어 있지 않다면, 더 따뜻한 날이 존재
# index를 이용해 더 따뜻한 날까지의 거리를 계산
if stack:
answer[i] = stack[-1] - i # 더 따뜻한 날까지의 거리 계산
# 현재 날을 스택에 추가
stack.append(i)
return answer
예제 입력 : temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
| 날짜 | 온도 | 스택 : 인덱스(온도) | answer | 설명 |
| 7 | 73 | [7(73)] | 0 | 마지막 날 : 더 따뜻한 날 없음 |
| 6 | 76 | [6(76)] | 0 | 현재 온도 > 스택의 온도 -> 스택 갱신 |
| 5 | 72 | [6(76), 72(5)] | 1 | 스택의 top이 더 따뜻함 |
| 4 | 69 | [6(76), 72(5), 69(4)] | 1 | 스택의 top이 더 따뜻함 |
| 3 | 71 | [6(76), 72(5), 71(3)] | 2 | 스택의 top에서 69 index 제거, 72가 더 따뜻함 |
| 2 | 75 | [6(76), 2(75)] | 4 | 71, 72 제거 -> 76이 더 따뜻함 |