[LC] 739. Daily Temperatures

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

Approach

monotonic stack을 이용하여 time complexity를 줄여야 하는 문제이다.

temperatures 배열을 순회하면서, 그 원소들을 감소하는 순서대로 해당하는 인덱스 값을 담는 stack을 사용한다.

단조적으로 증가/감소하는 값을 가진 stack을 monotonic stack이라 한다.

예를 들어, temperatures = [73,74,75,71,69,72,76,73]라면 다음과 같이 stack을 업데이트 해나가야 한다.

stack의 top부터 pop 해나가면서, 현재 보고있는 온도인 temp보다 값이 작다면, 현재 temp의 index i에서 stack[-1]에 저장된 index j를 뺀 값을 결과 리스트에 기록한다.

stack           현재 보고있는 값과 그 다음 값
-------------- -------------------------
(73)            73  <   74
0               0       1

(74)            74  <   75
1               1       2

(75)            75  >   71
2               2       3

(75  71)        71  >   69
2   3           3       4

(75  71  69)    69  <   72
2   3   4       4       5
=> 72가 들어갈 수 있도록, top에서부터 2개 pop

(75  72)        76  >   73
2   5           6       7
...

Complexity

Time: O(n) (temperatures의 모든 원소를 단 한 번씩 방문)
Space: O(n) (stack)

seungriyou / algorithm-study

[LC] 739. Daily Temperatures #90

Approach

Complexity

Monotonic Stack