[Medium] 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.

일별 온도를 나타내는 정수 배열이 주어지면, [i]라고 대답하는 배열 응답을 반환합니다. 이 답변은 더 따뜻한 온도를 얻기 위해 셋째 날 이후에 기다려야 하는 일 수입니다. 가능한 미래 요일이 없으면 대신 [i] == 0으로 답하십시오.

 

예시

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

 

해결 과정

처음에 이중 for문, two pointer 방식을 생각했었다.

하지만 이 문제는 Monotonic Stack을 사용하여 푸는 문제였기에 stack에 관한 풀이를 보고 공부해보았다.

마치 stack을 map처럼 2차 배열로 쌓아가는 방식이었다.

 

• 반환한 result 배열을 temperatures 길이만큼 선언한다.
• monoStack으로 사용할 배열을 선언한다.
• temperatures를 순회한다. 이때 방향은 right to left 이다.
  • 현재 값을 temp에 저장한다.
  • monoStack의 길이가 0이 될 때까지 & monoStack의 최상단 값이 현재 값보다 작거나 같을 때 monoStack을 pop 해준다.
  • 다음은 현재 idx와 monoStack의 가장 상단의 idx의 차이를 구하여 result[idx]에 값을 넣어준다. monoStack의 길이가 0이라면 0을 넣어준다.
  • 현재 값과 idx를 monoStack에 push한다.
• 순회를 마친 result 배열을 반환한다.

해결 코드

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const result = new Array(temperatures.length);
    const monoStack = [];
    
    for(let idx = temperatures.length - 1; idx >= 0; --idx) {
        const temp = temperatures[idx];
		
        while(monoStack.length && monoStack[monoStack.length - 1][0] <= temp) {
            monoStack.pop();
        }

        const numOfDays = monoStack.length ? (monoStack[monoStack.length - 1][1] - idx) : 0;
        result[idx] = numOfDays;

        monoStack.push([temp, idx]);
    }
    return result;  
};