# 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.

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`
`#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 << " ";}`

Some nice articles can be found:

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

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi