[LeetCode] 739. Daily Temperatures

739. Daily Temperatures

Medium

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

---

문제 풀이 

온도 배열이 주어진다. 

각 온도의 숫자가 자신의 위치에서 자신보다 높은 온도 위치의 거리 차이를 구해야한다.

높은 온도 위치의 거리를 구할때는 자신의 위치에서 가장 가까운 온도 위치로 계산한다.

처음 정답 배열에는 온도 배열 크기만큼 0을 할당하고, 각 온도를 탐색하면서 스택에 온도를 저장한다. 

값을 탐색하면서 큰 숫자가 나오지 않으면 답으로 0을 저장해야 하기 때문이다.

저장 되는 온도 값은 앞으로 탐색하게 되는 온도 값과 비교하여, 큰 값이 있다면 현재 탐색 위치인 인덱스에서 스텍의 인덱스 값을 빼어 답으로 저장하고 처리된 온도 값은 스텍에서 제거한다.

위 과정은 스텍이 빌때까지 진행된다.

참고로 스택에 들어가는 값은 인덱스이며 온도 값을 확인할때도 인덱스를 사용한다. 

소스 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans = [0] * len(temperatures)
        st = []
        for i, n in enumerate(temperatures):
            while st and temperatures[st[-1]] < n:
                ans[st[-1]] = i - st[-1]
                st.pop()
            st.append(i)
        return ans