1.单调队列的定义

单调队列顾名思义,就是具有单调性质和队列性质的数据结构.

2.单调队列的时间复杂度

单调队列可以保证,对于任何一个数而言,只会在队列中出现一次,一旦这个数对于最后答案没有贡献了,就会及时地将它删除.

一般来说,入队和出队操作满足以下两点.

  1. 入队操作:对于一个点而言,如果说它加入队列后满足队列的单调性质,那么我们就可以入队.
  2. 出队操作:对于一个点而言,如果说新加入的点,比它更加具有潜力,潜力一般指(拓展性更强,生存能力更高,节点入队时间短.)

因此单调队列的复杂度是我们除了常数复杂度O(1)O(1),O(log)O(log)复杂度级别,第三位最喜欢的线性复杂度O(n)O(n),因为这种算法往往代码短,思路好想,符合人类思维.

所以单调队列算法发明者相信,码量适中,思路精简,结构典型的单调队列,一定可以给你的程序员之旅一个有力的帮助.

3.单调队列适用于那些范围

单调队列,其实是单调栈的一个升级plus版本,或者说是具有[l,r]区间性质的单调栈.(注:单调栈一般来说是[0,r]类型的)

换句话来说,对于单调栈可以做出来的题目,基本上单调队列是可以操作出来的,而且请注意一点,单调队列适用范围更加广阔.
一般来说面对具有区间最优性质问题,并且具有两大性质,单调+队列的数据结构单调队列,往往都可以登上程序的数据结构优化的精彩舞台.

还有单调队列也是动态规划算法一个必备的优化手段,在NOIP,Acm,大公司面试题目中频频出现,所以我们有必要学会这种看似高端大气上档次的数据结构,实际上简易易懂的数据结构。

4.单调队列算法步骤

对于一个数而言,它可以从队尾入队,必须满足题目的特定条件。

对于一个队头的数而言,如果说新来的数,不仅是新来的具有潜力,而且又自身价值还比它价值高,那么不用说队头出队。

总而言之,队列的单调条件,性质如何设置,是我们解题的关键。

5.例题一：逛画展

例题传送门：https://www.acwing.com/problem/content/653/

题意分析：

就是你要求出一个区间[l,r],使得这个区间中有M张不同画师的名画,要求满足条件下,区间长度要最短.

思路解析：

程序=算法+数据结构.这道题目我们可以利用尺取法(也就是双指针法),当然我们也可以使用数据结构单调队列.
看到这道题目,我们显然要分析这道题目为什么可以用单调队列.

首先我们发现,对于一幅名画而言,如果我当前的候选门票区间,在候选区间的最左端,已经有了和它属于同一个画家的名画的话,那么我们显然是可以抛去之前的老画了,从原来的[l,r]–>[l+1,r+1][l,r]–>[l+1,r+1]

因为我现在还没有找到满足所有名家的画都看过的条件,那么我们显然是还要往后找的,但是我要求票价最小,所以说我们必须将[l,r]–>[l+1,r+1][l,r]–>[l+1,r+1]。

因为[l,r]–>[l+1,r+1][l,r]–>[l+1,r+1],不同名家画数量一样多,而且[l+1,r+1][l+1,r+1]比[l,r][l,r]更加具有潜力,拓展性

综上所述,我们这道题目一个隐藏的单调性质就出现了,在加上区间问题,必然具有队列性质,因此我们可以确定数据结构,单调队列无疑了.

切记:我们这里的单调条件就是:名画种类递增!

结构梳理:

如果说队头名画,在队列中还有另外一副和它同属一个画家,那么显然队头必须抛弃.

对于每一幅名画,它都可以入队.

对于每一个候选区间,如果它所有类型的名画都集齐了,那么我们就要统计区间费用.

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

deque<int> q;

int l, r, n, m, cnt;
int a[N], b[N];
int ans = 1e9, ansa = 1e9, ansb = 1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        if(!b[a[i]]) // 如果这幅画在队列中没有出现过，那么这幅画会使队列增加一种画家的画
            cnt++;
        q.push_back(i); // 名画入选
        b[a[i]] ++; // 记录所属画家的种类数
        while(b[a[q.front()]] >= 2) {// 这幅画的画家至少有2幅画在队列中
            b[a[q.front()]]--;
            q.pop_front(); //弹出队头的画
        }
        if(cnt >= m && q.back() - q.front() + 1 < ans) {
            ans = q.back() - q.front() + 1;
            ansa = q.front();
            ansb = q.back();
        } 
    }
    cout << ansa << " " << ansb <<endl;
}

6.例题二：切蛋糕

例题传送门：https://www.acwing.com/problem/content/654/

题意分析：
一句话题意:就是在长度为N的区间里面,找一个长度为K的区间,要求区间的权值最大!

对于这道题目而言,我们依旧需要按照程序=算法+数据结构的思维考虑,不过这一次我们可以直接发现这道题目需要使用单调队列.
因为我们发现这道题目,具有以下两点性质.

  1. 区间最值问题,而且具有滚动的条件,单调队列的特性.
  2. 队列性质,这道题目可以看作一个区间队列.

既然这道题目是区间最值,那么我们可以想到要用单调队列,当时有几个问题如下所示.

  1. 我们如何利用单调队列优化?
  2. 如何找出这道题目的单调性质是上升还是递减?
  3. 单调队列入队出队怎么判断?

首先面对第一个问题,对于单调队列优化,我们可以将区间的值,设置为单调队列每一个元素,既然这样的话,那么第二问题,我们也可以迎刃而解,当然是单调递增的序列.
接着面对第三个问题,入队出队判断.

  1. 入队:对于入队操作而言,当然也是所有元素都可以入队.
  2. 出队:对于出队操作而言,有一点小小的变化.

首先我们发现,只要当前队列中,队头元素的已经老了,或者说当前队列超过了m个元素,那么我们必须将队头出队.
如果我们发现队列中队尾开始无法满足单调递增了,那么显然破坏了单调性质,我们必须将他们出队.

下面，我们用单调队列维护一个区间内的前缀和。

Code:

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int head, tail;
int l, r, n, m;
int ans = -1e9;
int a[N], s[N];

int main()
{
    ios::sync_with_stdio(false);
    deque<int> q;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    q.push_back(0);
    for(int i = 1; i <= n; ++i) {
        while(q.size() && q.front() < i - m) q.pop_front();
        if(q.size()) ans = max(ans, s[i] - s[q.front()]);
        while(q.size() && s[i] <= s[q.back()]) q.pop_back();
        q.push_back(i);
    }
    cout << ans <<endl;
    return 0;
}