class Solution {
    
    // 더 따뜻한 온도를 얻기 위해 기다려야 하는 일수
    // Monotonic Stack
    // O(n)
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];

        // * 반복을 한번만 하기위해서 날짜값(인덱스)을 저장해 둔다(가장 최근일자 저장)
        Stack<Integer> stack = new Stack<>();

        for (int currDay = 0, prevDay = 0; currDay < temperatures.length; currDay++) {
            // 현재온도가 스택의 값보다 크면 
            while (!stack.isEmpty() && temperatures[currDay] > temperatures[stack.peek()]) {
                // 스택에서 제거하고
                prevDay = stack.pop();
                // 날짜값의 차이를 결과에 저장한다. 
                ans[prevDay] = currDay - prevDay;
            }
            stack.add(currDay);
        }

        return ans;
    }
}