单调栈与单调队列一般存在以下三种形式：存值，存下标，数组实现，数组实现的优点在于在清空栈时只需top=0即可

单调栈

伪代码：

1
2
3
4
5
6
7
8
for(i=1->n)//n为元素数量
{
    ① while(栈非空且入栈元素优于栈顶元素)栈顶出栈//维持栈的单调性
    //while结束的两种可能的判断
    ② 如果(栈顶元素优于入栈元素)更新一次答案，此时栈顶即为最优解
    否则 不存在答案
    ③ 将新元素入栈
}

eg:输入n个数字 输出每个数字左侧距离该数字最近的比它小的元素，不存在则输出-1
in 5
7 8 5 6 7
out -1 7 -1 5 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//存值
int a[N],ans[N];//a[N]用来存放输入的数字，ans[N]用于存放答案
stack<int> stk;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
    while(stk.size()&&stk.top>=a[i])stk.pop();
    if(stk.empty())ans[i]=-1;
    else ans[i]=stk.top();
    stk.push(a[i]);
    cout<<ans[i]<<' ';
}   
//存下标＋数组实现
int a[N],stk[N],ans[N],top;//stk数组用来模拟下标
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
    while(top&&a[stk[top]]>=a[i])top--;
    if(top) ans[i]=a[stk[top]];
    else ans[i]=-1;
    stk[++top]=i;
    cout<<ans[i]<<' ';
}

单调队列

通过deque实现，在队头进行出队操作，在队尾进行入队和出队操作，最典型的是用于处理滑动窗口
伪代码：

1
2
3
4
5
6
7
for(i=1->n)
{
    ① while(非空且队头不合法)弹出头//队头合法性
    while(非空且i优于队尾)弹出尾//队尾优越性
    ② 将i入队
    ③ 此时队头为最优
}

例题

1
2
3
4
5
6
7
8
9
10
//deque存下标实现
for (int i = 1; i <= n; i++)
{
    //滑动窗口的区间为[i-k+1,i]
    while (dq.size() && dq.front() < i - k + 1)dq.pop_front();
    while (dq.size() && a[i]<= a[dq.back()])dq.pop_back();
    dq.push_back(i);
    //当第一个滑动窗口开始形成时，开始输出答案
    if (i >= k)cout << a[dq.front()] << ' ';
}

#TODO 数组模拟