[알고리즘] Leetcode_739_Daily_Temperatures

Problem

Solve

import java.util.*;
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[n];

        for(int i = 0 ; i < n ; i++){
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
            //Monotonic Stack
            //peek 인덱스 배열값보다 현재의 값이 클 때까지 i 증가시킴
                int peek = stack.pop();
                answer[peek] = i - peek;
            }
            stack.add(i);
            //stack 에 넣어줄 값은 인덱스
        }
        return answer;
    }
}

우리가 결론적으로 도출해야하는 값은 자기 자신보다 큰 온도가 등장했을 때의 날짜 차이이다. 즉, 인덱스 차이라고 할 수 있다. 따라서 인덱스와 온도값을 비교해야 하므로 stack 에는 Index 값으로 처리할 수 있게 하고, peek 값을 통해 배열에 접근할 수 있도록 했다.
for 문으로 모든 배열의 값을 순회하면서 stack의 peek 보다 값이 크다면 pop하고 결과값을 인덱스로 도출하여 작은 값을 찾을 때까지 반복하였다.
반대로 작다면 그냥 stack에 추가하였다.
그렇게 모두 순회하고 난 후, stack에 아직 값이 남아있다면 배열의 값보다 큰 온도값을 찾지 못했다는 의미이므로 0으로 결론 낸다.

⭐️ Monotone Stack

몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉으로, 기본적인 아이디어는 스택의 원소들을 오름차순, 혹은 내림차순 상태를 유지하도록 하는 것입니다.