均可用deque模拟实现，操作简单易懂

单调队列（以滑动窗口为例）

acwing156 滑动窗口

题目描述

给定一个大小为 n≤106 的数组。有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N =1e6+10;
int a[N];
int n;int k;
int main()
{
    cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];
    deque<int> q;
    //min
    for(int i=1;i<=n;i++)
    {
        while(q.size()!=0 && a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        if(i - q.front() >= k) q.pop_front();
        if(i>=k) cout<<a[q.front()]<<' ';
    }
    cout<<'\n';
    //max
    q.clear();
    for(int i=1;i<=n;i++)
    {
        //加入的元素若比队尾元素大，则将队尾元素出队
        while(q.size()!=0 && a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        //判断队头元素是否已经滑出窗口
        if(i - q.front() >= k) q.pop_front();
        if(i>=k)cout<<a[q.front()]<<' ';
    }
    cout<<'\n';
    return 0;
}

单调栈（以acwing830为例）

acwing830 单调栈

#### 题目描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 -1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出 -1。
数据范围
1 ≤ N ≤ 1e5,1 ≤ 数列中元素 ≤ 1e9

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2


----------

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;
int a[N];
int main()
{
    int n;cin>>n;
    deque<int> s;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(s.size()!=0 && a[s.back()] > a[i]) s.pop_back();
        if(s.size() == 0) cout<<-1<<' ';
        else cout<<a[s.back()]<<' ';
        s.push_back(i);
    }
    return 0;
}

acwing4964.子矩阵的和