Monotonic Stack

Monotonic stack is special kind of stack, in which elements are placed in monotonic order.

For example, there is monotonic increasing stack, which means elements are always in increasing order(from top to bottom). If the new elements larger then element currently on top, you need to pop the top element first and then push the new elements.

Below is simple example for a monotonic increasing stack.

class MonotonicStack {

    private stack: number[];

    constructor() {
        this.stack = [];
    }

    push(v: number) {
        while (this.stack.length > 0 && v > this.stack[this.stack.length - 1]) {
            this.stack.pop();
        }
        this.stack.push(v);
    }

    pop(): number | undefined {
        return this.stack.pop();
    }
}

const monotonicStack = new MonotonicStack();
monotonicStack.push(1);// MonotonicStack { stack: [ 1 ] }
console.log(monotonicStack);
monotonicStack.push(3);// MonotonicStack { stack: [ 3 ] }
console.log(monotonicStack);
monotonicStack.push(5);// MonotonicStack { stack: [ 5 ] }
console.log(monotonicStack);
monotonicStack.push(4);// MonotonicStack { stack: [ 5, 4 ] }
console.log(monotonicStack);
monotonicStack.push(2);// MonotonicStack { stack: [ 5, 4, 2 ] }
console.log(monotonicStack);
monotonicStack.push(0);// MonotonicStack { stack: [ 5, 4, 2, 0 ] }
console.log(monotonicStack);

Daily Temperatures

The problem is to find the number of days before a new temperature comes.

We can brute force it using 2 for loops. In this way, the time complexity is O(n^2).

Actually, this problem fits very well with the features of monotonic stack.

We can create a monotonic stack to save elements and its index. Every time a new temperature comes, if it's warmer, then we can compare it one by one with the elements in stack to get the result. If it's colder, then just push it into the stack, and wait for a new warmer day comes.

Below show a basic process for this method.

[30,40,20,10,50]

loop the array

index: 0, cur:30, 
    push, stack: [(30, 0)]

index: 1, cur:40, 
    cur>stack[top][0], pop (30,0), result[0]=1-0
    stack.length === 0, push 40, stack: [(40,1)], 

index: 2, cur:20, 
    cur<stack[top][0], push, stack: [(40,1),(20,2)]

index: 3, cur:10, 
    cur<stack[top][0], push, stack: [(40,1),(20,2),(10,3)]

index: 4, cur:50, 
    cur>stack[top][0], pop (10,3), result[3]=4-3
    cur>stack[top][0], pop (20,2), result[2]=4-2
    cur>stack[top][0], pop (40,1), result[1]=4-1
    stack.length === 0, push, stack: [(50,4)]

last result, result[4] always 0

Now let's implement it in code.

function dailyTemperatures(temperatures: number[]): number[] {
    let stack: number[][] = [];
    let result: number[] = Array.from({length: temperatures.length}, _ => 0);

    for (let i = 0; i< temperatures.length; i++) {
        while(stack.length > 0 && temperatures[i] > stack[stack.length-1][0]) {
            // warmer day comes, get results
            const v = stack.pop() as number[];
            result[v[1]] = i - v[1];
        }

        // colder day, save it for later
        stack.push([temperatures[i], i])
    }
    return result;
};

const temperatures = [73,74,75,71,69,72,76,73];
console.log(dailyTemperatures(temperatures));