해당 문제는 “주식”문제와 비슷한 형태로 구성되어있으며, 오늘 이후에 더 따뜻한 날이 언제 찾아오는지를 각 날짜마다 리턴하여 주는 문제라고 볼 수 있다.
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^530 <= temperatures[i] <= 100해당 문제에서 현재 온도에 대한 배열 길이를 10^5로 제한해두었다는 것은 지난 강의에서 배웠던 10^8의 시간 복잡도 제한을 넘기지 못하도록 구성했다는 것과 같은 의미이므로, 해당 문제는 중첩 반복문이 발생하면 안된다는 것을 알 수 있다.
따라서, 우리는 스택 자료구조를 이용하여 문제를 풀이할 것이다.
O(n)