Mono Queue and Mono Stack

A monotonic stack is a stack whose contents are kept in strictly increasing or strictly decreasing order from bottom to top. Before pushing a new value, any existing top elements that would violate the ordering are popped.

A monotonic queue (usually implemented with a deque) extends the same idea to a sliding window: values are pushed on the right and dropped from the left once they leave the window.

The canonical problem shown below is "next greater element": for each index $i$ in an array, find the smallest index $j > i$ with nums[j] > nums[i], or $-1$ if no such index exists. A decreasing monotonic stack of pending indices solves it in a single left-to-right pass.

There will be some cases we have right-to-left pass, then we fill the initial value with the length of the array, and then we can find the next smaller element as the left case.

Mono stack

A mono stack is a stack that only allows the elements to be pushed in decreasing/increasing order.

This structure is useful when the increment/decrement of the elements is the only thing we are caring about.

For example, when we use interval editing to construct the array, we only care about the increment/decrement of the elements.

Since craving a hole is equivalent to create a new heap.

Codes

Python
C++

def solve(xs):
    nums = xs
    n = len(nums)
    ans = [-1] * n
    stack = []  # indices with strictly decreasing values
    for i, v in enumerate(nums):
        while stack and nums[stack[-1]] < v:
            ans[stack.pop()] = i
        stack.append(i)
    return ans

#include <stack>
#include <vector>

std::vector<int> solve(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> ans(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

Example

Loading Python runner...

Description

Run time analysis

$O(n)$ . Each index is pushed onto the stack exactly once and popped at most once, so the total work over the outer loop and all inner while iterations is bounded by $2n$ .

Space analysis

$O(n)$ auxiliary for the stack in the worst case — a strictly decreasing input never triggers any pops, so every index stays on the stack until the end.

Proof of correctness

Maintain the invariant "the stack holds indices of elements whose next greater element has not yet been found, in strictly decreasing order of value from bottom to top". When processing index $i$ with value $v$ , any stack top $j$ with nums[j] < v has found its answer: $i$ is the earliest later index with a strictly greater value, because every index between $j$ and $i$ that was ever pushed has already been popped (otherwise it would still be on the stack and lie below $i$ , violating monotonicity). Popping $j$ and recording ans[j] = i preserves the invariant. After pushing $i$ the stack is still decreasing. Indices remaining on the stack at the end keep the default $-1$ , which is correct because no later element ever exceeded them.

Extensions

Applications

Monostack

Leetcode 1526

Leetcode 1526

Intuition

We only need to care about the increment/decrement of the elements, so we can use a mono stack to keep track of the elements that are not yet filled.

Solution

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        # use mono stack
        st=[0]
        res=0
        for i in target:
            if i==st[-1]:
                continue
            elif i<st[-1]:
                while i<=st[-1]:
                    st.pop()
                st.append(i)
            else:
                res+=i-st[-1]
                st.append(i)
        return res

Leetcode 84 [Expected difficulty: 13]

Leetcode 84

Intuition

Construction for mono stack is $O(n)$ , and we can use the mono stack to find, suppose our $i$ -th element is the minimal element in the rectangle, then we can find the left and right boundary of the rectangle, and calculate the area (greedy principle).

Solution

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # two mono stack actually, query: for each i, if we use the ith height to maximal, what is the bigest rectangle we can have
        n=len(heights)
        # right[i] denotes the index of the next small element on the right
        # if right[i]==n, it means there is no smaller element on it's right
        right=[n]*n
        st=[]
        # enumerate from left to right, i > stack.pop() guarenteed.
        for i in range(n):
            while st and heights[st[-1]] > heights[i]:
                right[st.pop()] = i
            st.append(i)
        
        # left[i] denotes the index of the next small element on the left
        # if left[i]==-1, it means there is no smaller elements on it's left
        left=[-1]*n
        st=[]
        for i in range(n-1,-1,-1):
            while st and heights[st[-1]] > heights[i]:
                left[st.pop()] = i
            st.append(i)

        res=0
        for i in range(n):
            l,r=left[i],right[i]
            # print(l,r,heights[i])
            res=max(heights[i]*(r-l-1),res)
        return res

Leetcode 2281 [Expected difficulty: 14]

Leetcode 2281

Intuition

We can use a monotonic stack to keep track of left and right boundaries of the elements, and then use prefix sum to calculate the contribution for each element, as the minimal, to the total strength.

Solution

class Solution:
    def totalStrength(self, strength: List[int]) -> int:  
        # reference lee's solution. I'd call this full version of mono stack.
        
        M=10**9+7
        n=len(strength)

        # right[i] denotes the index of the next small element on the right
        # if right[i]==n, it means there is no smaller element on it's right
        right=[n]*n
        st=[]
        # enumerate from left to right, i > stack.pop() guarenteed.
        for i in range(n):
            while st and strength[st[-1]] > strength[i]:
                right[st.pop()] = i
            st.append(i)
        
        # left[i] denotes the index of the next small element on the left
        # if left[i]==-1, it means there is no smaller elements on it's left
        left=[-1]*n
        st=[]
        for i in range(n-1,-1,-1):
            # warning: eq sign used to ensure that we don't stop on 13(1) since only (1)3 will be count on right
            while st and strength[st[-1]] >= strength[i]:
                left[st.pop()] = i
            st.append(i)

        res=0
        # compute prefix of prefix array
        # for each minimal ele at index i in array (sum of all subarray including ele as smallest element is)
        #   sum([sum[cl:cr] for cl in range(l,i) for cr in range(i,r))
        # = sum([[pfx[cr]-pfx[cl] for cl in range(l,i)] for cr in range(i,r)])
        # = sum(pfx[cr] for cr in range(i,r))*(r-i)-sum(pfx[cl] for cl in range(l,i))*(i-l)
        # = (ppfx[r]-ppfx[i])*(i-l)-(ppfx[i]-ppfx[l])*(r-i)
        res=0
        pfx=[0]
        for i in strength:
            pfx.append(pfx[-1]+i)
        ppfx=[0]
        for i in pfx[1:]:
            ppfx.append(ppfx[-1]+i)
        for i in range(n):
            l,r=left[i],right[i]
            # note that l might be -1
            lacc,racc=ppfx[i]-ppfx[max(0,l)],ppfx[r]-ppfx[i]
            rn,ln=r-i,i-l
            res+=strength[i]*(racc*ln-lacc*rn)
        return res%M

References

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 10 (Stacks and Queues).
cp-algorithms — Sparse table

Mono stack​

Codes​

Example​

Description​

Run time analysis​

Space analysis​

Proof of correctness​

Extensions​

Applications​

Monostack​

Leetcode 1526​

Leetcode 84 [Expected difficulty: 13]​

Leetcode 2281 [Expected difficulty: 14]​

References​

Mono stack

Codes

Example

Description

Run time analysis

Space analysis

Proof of correctness

Extensions

Applications

Monostack

Leetcode 1526

Leetcode 84 [Expected difficulty: 13]

Leetcode 2281 [Expected difficulty: 14]

References