[leetcode] Daily Temperatures

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 

 

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

        for(int i=temperatures.length - 1; i>=0; i--) {
        
        	//현재 인덱스보다 낮거나 같은 온도를 가진 모든 인덱스 pop
            while(!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }

			//stack에 element가 있다면 다음으로 높은 온도가 존재
            if(!stack.isEmpty()) {
                answer[i] = stack.peek() - i;
            }

            stack.push(i);
        }

        return answer;
    }
}

 

Monotonic Stack
Whenever a problem requires enumerating values for indices on the basis of other values in an array, one should think of including a stack in the solution! And that too, a monotonic stack. It is simply a stack which contains values in a monotonic order; i.e either increasing or decreasing.
Imagine there is a data structure which contains the indices whose temperatures are in an increasing order. Then, enumerating the next index which has a greater temperature will be easy: we simply pop the elements till the top element has a greater temperature than the current index! Refer to the following picture for better understanding.

Imagine that the stack contains the indices {4, 5, 6, 7, 8} which have temperatures {10, 12, 14, 18, 20}. We are traversing from reverse and are currently at index 3 which has a temperature of 16 (indicated by the grey block). To find the next index with a greater temperature, we simply pop from the top of the stack till we encounter a warmer index! Hence all the red blocks are popped, i.e, the stack finally contains {7, 8}. Clearly, the next warmer index for the current index is 7. Finally, the current index is pushed in the stack and monotonicity is maintained.

It becomes rather intuitive once you take a few examples yourself :)