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

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.

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

Data Scientist/MLE/SWE @takemobi