Stack - ashishranjandev/interview-wiki GitHub Wiki

A monotonic stack is a stack data structure that is used to solve problems related to finding the next greater or smaller element in an array. It is a variation of the regular stack data structure that maintains either an increasing or decreasing order of elements.

As we need monotonically increasing stack, we should not have a smaller element at top of a bigger element. So Iterate the given list of elements one by one :
Before pushing into the stack, POP all the elements till either of one condition fails:
       1. Stack is not empty
       2. Stack’s top is bigger than the element to be inserted.
Then push the element into the stack.

Consider an array Arr[] = {1, 4, 5, 3, 12, 10}
For i = 0: stk = {1}
For i = 1: stk = {1, 4}
For i = 2: stk = {1, 4, 5}
For i = 3: stk = {1, 3}  [pop 4 and 5 as 4 > 3 and 5 > 3]
For i = 4: stk = {1, 3, 12}
For i = 5: stk = {1, 3, 10} [pop 12 as 12 > 10] 

Solution for next higher temperature

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] output = new int[temperatures.length];
        Stack<Integer> temperatureStack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!temperatureStack.empty() && temperatures[temperatureStack.peek()] < temperatures[i]) {
                output[temperatureStack.peek()] = i - temperatureStack.pop();
            }
            temperatureStack.push(i);
        }
        return output;
    }
}