单调队列

常见模型：找出滑动窗口中的最大值/最小值

是一种主要用于解决滑动窗口类问题的数据结构，即在长度为n 的序列中，求每个长度为 k的区间的区间最值。

用于解决滑动窗口和双指针解决不了的问题

https://www.bilibili.com/video/BV1H5411j7o6

滑动窗口

求最大值三种情况：

队尾入队：

​ 如果新进入窗口的值大于队尾元素，则队尾出队列，再将将新进入的元素入队

​ 否则直接入队

队头出队：

​ 若队头是否滑出了窗口，队头出队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int a[N];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
    deque<int> q;
    for(int i = 1; i <= n; i++)
    {
        while(q.size() && q.back() > a[i]) //新进入窗口的值小于队尾元素，则队尾出队列
            q.pop_back();
        q.push_back(a[i]);//将新进入的元素入队
        if(i - k >= 1 && q.front() == a[i - k])//若队头是否滑出了窗口，队头出队 
            q.pop_front();
        if(i >= k)//当窗口形成，输出队头对应的值
            cout << q.front() <<" ";
    }
    q.clear();
    cout << endl;

    //最小值亦然
    for(int i = 1; i <= n; i++)
    {
        while(q.size()&&q.back()<a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i-k>=1&&a[i-k]==q.front()) q.pop_front();
        if(i>=k) cout<<q.front()<<" ";

    }
}

滑动窗口的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;
        for(int i =0;i<nums.size();i++){
            while(q.size()&&q.back()<nums[i]) q.pop_back();
            q.push_back(nums[i]);
            if(i-k>=0&&nums[i-k]==q.front()) q.pop_front();
            if(i>=k-1) ans.push_back(q.front());
        }
        // int q[100010];
        // int h = 0,t = 0;
        // for(int i = 0;i<nums.size();i++){
        //     if(h<=t&&q[h]<i-k+1) h++;
        //     while(h<=t&&nums[i]>=nums[q[t]]) t--;
        //     q[++t] = i;
        //     if(i>=k-1) ans.push_back(nums[q[h]]);
        // }
        return ans;
    }
};

单调队列习题集

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

1、题目（来源于AcWing）：

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式 第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。

输出格式 共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。

数据范围 1≤N≤105 1≤数列中元素≤109

输入样例： 5 3 4 2 7 5 输出样例： -1 3 -1 2 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
stack<int> stk;

int main()
{
    int m;
    cin >> m;    
    while (m -- )
    {
        int x;
        cin >> x;       
        while (stk.size() && stk.top() >= x) stk.pop();//在x入栈前删掉比x大的数        
        if (stk.size() == 0) cout << "-1 ";
        else cout << stk.top() << ' ';        
        stk.push(x);//x入栈
    }   
    return 0;
}

直方图中最大的矩形

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], q[N], l[N], r[N];
//l[i]表示i左边第一个比h[i]小的元素的下标，r[i]表示i右边第一个比h[i]小的元素的下标
typedef long long LL;   
int main()
{
    int n;
    while(cin>>n, n)
    {
        for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);
        stack<int> st;
        for(int i = 1; i <= n; i ++)
        {
            while(st.size()&&h[st.top()]>=h[i])  st.pop();
            if(st.size() == 0) l[i]=0;
            else l[i]=st.top();
            st.push(i);
        }
        stack<int> st2;
        for(int i = n; i>=1; i --)
        {
            while(st2.size()&&h[st2.top()]>=h[i])  st2.pop();
            if(st2.size() == 0) r[i]=n+1;
            else r[i]=st2.top();
            st2.push(i);
        }
        LL res = 0;
        for(int i = 1; i <= n; i ++)  
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}

单调栈习题集