[LeetCode] 739. Daily Temperatures (java)

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

 

문제 파악

다음 따뜻한 날까지의 날짜 차이를 계산하는 문제

 

 

문제 풀이

Stack

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Entry> stack = new ArrayDeque<>();
        
        for (int curr = 0; curr < temperatures.length; curr++) {
            while (!stack.isEmpty() && stack.peek().temperature < temperatures[curr]) {
                    Entry past = stack.pop();
                    answer[past.day] = curr - past.day;
            }
            stack.push(new Entry(temperatures[curr], curr));
        }

        return answer;
    }

    class Entry {
        int temperature;
        int day;

        Entry(int temperature, int day) {
            this.temperature = temperature;
            this.day = day;
        }
    }
}

 

📊 실행 결과

• 시간 복잡도: O(n)

 

 

Note

• 미래의 데이터에 따라 과거에 대한 값이 결정된다! 👉 Stack 자료구조 활용하기