Topic 2: Monotonic stack or deque

shangping guo

5180

Monotonic stack or deque

monotonic stack/deque is often used to implement O(N) algorithm (generally need O(N^2) otherwise).

when need push/pop from both ends, we need use monotonic deque.

this topic is generally hard, and not intuitive. It is critical to understand why we do this.

monotonic stack problem is mostly previous/next smaller/larger problems.

Next smaller/larger problems

find the right first element which smaller or greater than current element.

for next smaller: use monotonic increasing stack. When iterating to the right, if current element is smaller than stack top, then we get the first smaller elements for the stack top.
for next greater: use monotnic decreasing stack and similar as above.
generally we store index in the stack.
each element is pushed once and poped once.

Previous smaller/larger problem.

this is to find the left first elment which is smaller/larger than current element.
This can be converted to equivalent next larger/smaller problem.
why we need this? It can be applied in search the valid subarray to have the left and right the first previous smaller/larger and right first smaller/larger.

Find the range for previous and next smaller/larger.

This can be solved using sliding window O(N^2).

for finding previous and next smaller:
using monotonic increasing stack, when we iterate to the right, and the element is smaller than stack top, then we update all the stack elements > current (current element is the first smaller). Also when the current element is able to push into the stack, we find the previous smaller for the current element.

example:
907 Sum of Subarray Minimums 33.3% Medium
return the sum of all subarray minimum.
idea: each element can be the minimum for some subarray. If we can find the next smaller and previous smaller for each element, then we get the subarray length for each element as the minimum.

    int sumSubarrayMins(vector<int>& A) {
        stack<int> st;
        int n=A.size();
        vector<int> left(n),right(n);//max length
        for(int i=0;i<n;i++) {
            left[i]=i+1;
            right[i]=n-i;
        }
        //get previous less and next less
        //increasing order
        for(int i=0;i<A.size();i++){
            while(st.size() && A[i]<A[st.top()]){
                int tp=st.top();st.pop();
                right[tp]=i-tp;
            }
            if(st.size()) left[i]=i-st.top(); //else no change
            
            st.push(i);
        }
        long ans=0;
        int mod=1e9+7;
        for(int i=0;i<A.size();i++){
            ans+=(long)left[i]*right[i]*A[i]%mod;
            ans%=mod;
        }
        return ans;
    }

Monotonic increasing/decreasing deque

monotonic deque is often combined with sliding window with min/max.
general approach:

the front stores the min or max, and we add new elements to the back and keep the deque in increasing (max problem) or decreasing (min problem).
pop old front elements when it is out of window.
each element is pushed and popped once (either front or back)
store index instead of values in the deque.

- 239 Sliding Window Maximum 44.1% Hard

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //monotonic array using deque
        vector<int> res;
        deque<int> dq;
        for(int i=0;i<nums.size();i++)
        {
            if(!dq.empty() && dq.front()==i-k) dq.pop_front();
            while(!dq.empty() && nums[dq.back()]<nums[i]) dq.pop_back(); //remove all elements less than it
            dq.push_back(i);
            if(i>=k-1) res.push_back(nums[dq.front()]);
        }
        return res;
    }

- 862 Shortest Subarray with Sum at Least K 24.9% Hard
with negatives.
- get the prefix sum
- range sum = prefix[i]-prefix[j] with j<i.
- keep visited prefix sum in decreasing deque. pop all those front elements satisfying the condtion. (they are not needed since right elements will not be able to get shorter using these old values)
- new elements can pop those larger than it since the old larger values cannot contribute shorter.

Please upvote it if it is helpful so that more people can see it. Thanks

Comments (5)