Using monotonic stack to solve some questions

We can use the monotonic stack to solve some problems in O(n) efficiently. We have several such kinds of questions can be solved by using the Monotonic stack.

AcWing 830 monotonic stack

A nice explanation can be found here. The gif is pretty nice, although some part of the vis is in Chinese. Basically, that problem is trying to find the previous minimum value. If not, return -1. The vis is using the example of

3, 4, 2, 7, 9

Code

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{
    int n, num;
    vector<int> nums;
    cin >> n;
    for (int i = 0; i < n;++i) 
    {
        cin >> num;
        nums.push_back(num);
    }
    stack<int> stk;
    stk.push(-1); /*Make sure the stack will not empty*/
    vector<int> ret;
    for (auto x : nums) 
    {
        while(stk.top() >= x)
            stk.pop();
        ret.push_back(stk.top());
        stk.push(x);
    }
    for (auto x: ret) cout << x << " ";
}

AcWing 3516 the maximum area in a binary matrix.

Some nice articles can be found:

Two pointer and deque

Monotonic queue

https://jimmy-shen.medium.com/sliding-window-min-max-priority-queue-monotonic-queue-ec77636cdc31