[leetcode #739] Daily Temperatures

Problem

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 <= 10⁵
・ 30 <= temperatures[i] <= 100

Idea

못 풀긴 했는데 정말 재밌는 문제였다. 현재 날씨로부터 며칠이 지나야 따뜻해지는지 확인하는 문제다.

Stack을 이용해서 문제를 풀 수 있는데, stack에는 각 날짜의 index를 저장한다.

온도를 탐색하면서 stack에서 현재 온도보다 높은 온도가 나올 때까지 pop을 하면 된다. stack에 저장되어 있는 날짜의 온도가 현재 온도보다 작다는 뜻이기 때문이다. pop을 하면서 현재 날짜의 index에서 stack에 저장되어 있는 index를 뺀 값을 답에 저장하면 된다.

Stack이 비어 있거나 현재 온도가 stack의 온도보다 낮으면 stack에 현재 날짜의 index를 push한다.

전체 온도를 전부 탐색하고 난 뒤 답으로 저장한 array를 리턴하면 된다.

Solution

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i=0; i < n; i++) {
            int currentTemp = temperatures[i];
            while (!stack.isEmpty() && currentTemp > temperatures[stack.peek()]) {
                int prevDay = stack.pop();
                answer[prevDay] = i - prevDay;
            }
            stack.push(i);
        }

        return answer;
    }
}

Reference

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