优先队列

优先队列可以完成以下操作:

  • 插入一个数值
  • 取出最小的数值(获得数值,并且删除)

在之前的堆排序,我们已经初步引出了优先队列的概念。

优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,而是将当前队列中最大的元素出队。元素的比较规则默认按元素值由大到小排序,可以重载“<”操作符来重新定义比较规则。

声明方式

1
2
3
4
5
6
7
8
priority_queue <int> q;
priority_queue <double> q;

priority_queue <node> q;
priority_queue<int, vector<int>, cmp>q;

priority_queue <int,vector<int>,greater<int> > q;
priority_queue <int,vector<int>,less<int> >q;

排序特性

自动排序

在堆排序文章里,我们了解到的是优先队列的最普通形式,按从大到小排列。

但是,日常的使用时,我们总不可能一直使用从大到小的排列方式吧?那我们应该怎么办呢?

自定义优先级

无论是C的qsort,还是C++的sort,我们都可以使用cmp函数来自定义排序规则。那么,在优先队列中,是否也可以使用cmp函数呢?

答案是肯定的。

1
2
3
4
bool cmp(int a,int b){
return a < b;
};
priority_queue<int, vector<int>, cmp>q;

less和greater优先队列

1
2
3
4
5
//从大到小
priority_queue <int,vector<int>,less<int> > q;
//从小到大
priority_queue <int,vector<int>,greater<int> > q;

结构体重载

1
2
3
4
5
6
7
8
//operator< 重载
struct node{
int x,y;
bool operator < (const node & a) const{
return x < a.x;
}
};//y为值, x为优先级。
priority_queue <node> q;
1
2
3
4
5
6
7
8
//operator< 重载
struct node {
int x, y;
bool operator < (node a, node b){
return a.x > b.x; //结构体中,x小的优先级高
}
}; //y为值, x为优先级。
priority_queue<node>q; //定义方法

例题

合并果子

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n1n-1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为11 ,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有33 种果子,数目依次为112299 。可以先将1122 堆合并,新堆数目为33 ,耗费体力为33 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为1212 ,耗费体力为1212 。所以多多总共耗费体力=3+12=15=3+12=15 。可以证明1515 为最小的体力耗费值。
这是一道典型的优先队列题目。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
long long m,n,sum;
priority_queue<int,vector<int>,greater<int> >q;

int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0;i < n;i++) cin >> m,q.push(m);
for(int i = 1;i < n;i++){
m = q.top();
q.pop(),
m += q.top();
q.pop();
sum += m;
q.push(m);
}
cout << sum << "\n";

return 0;
}

序列合并

有两个长度都是 N 的序列 A 和 B ,在 A 和 B 中各取一个数相加可以得到N2N^2 个和,求这N2N^2 个和中最小的 N 个。

输入格式

第一行一个正整数 N;

第二行N个整数AiA_i , 满足AiAi+1A_i \le A_{i+1}Ai109A_i \le 10^9;

第三行N个整数BiB_i , 满足BiBi+1B_i \le B_{i+1}Bi109B_i \le 10^9;

1N1000001 \le N \le 100000

输出格式

输出仅一行,包含N个整数,从小到大输出这N个最小的和,相邻数字之间用空格隔开。

思路

题意很明了,我们只需要将 A 和 B 序列数字的和压入堆中,并取前 N 个和即可。但是,很明显,在遇到数据过于 毒瘤 大的情况时,显然时间复杂度会达到O(n2logn)O(n^2logn) ,显然超时。

因为两个序列是递增的,如若Ai+BjA_i + B_j 没有放入优先队列,那么Ai+Bj+1A_i + B_{j + 1} 呢?

答案是很显然易见的,并不会放入优先队列。因为 B 序列满足BiBi+1B_i \le B_{i+1} ,所以Ai+Bj+1>Ai+Bj>q.top()A_i + B_{j + 1} > A_i + B_j > q.top()

所以Ai+BjA_i + B_j 没有放入优先队列时,Ai+Bj+n(n>0)A_i + B_{j + n}(n > 0) 也都不会被放入,可以直接 break ,跳转到Ai+1+BiA_{i + 1} + B_i 继续枚举。

时间复杂度证明

第一行至多扫完它的11\dfrac{1}{1} ,第二行变为12\dfrac{1}{2}

由此类推,第i行最多1i(1in)\dfrac{1}{i}(1 \le i \le n)

合在一起,共11+12++1n\dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{n}

欧拉证明过,上面的无穷级数的增长率为O(lnn)O(lnn)

因此,总复杂度为O(n logn lnn)O(n\ logn\ lnn) ,即O(nlog2n)O(nlog^2n) 的,证毕

代码
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
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int>q;
int n,a[100005],b[100005],ans[100005];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++) scanf("%d",&b[i]);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(q.size() < n) q.push(a[i] + b[j]);
else{
if(q.top() > a[i] + b[j]){
q.pop();
q.push(a[i] + b[j]);
}
else{
break;
}
}
}
}
for(int i = n;i >= 1;i--){
ans[i] = q.top();
q.pop();
}
for(int i = 1;i <= n;i++) printf("%d ",ans[i]);
return 0;
}
巧妙的方法

ij>ni*j>n 时,Ai+BjA_i+B_j 一定不是前 n 小的数。

因为两个序列均有序,所以如果x<=ix<=iy<=jy<=j 那么Ax+By<Ai+BjA_x+B_y<A_i+B_j 。于是至少有iji*j 个数小于等于Ai+BjA_i+B_j 。当ij>ni*j>n 时,一定有多余 n 个数小于等于Ai+BjA_i+B_j ,所以Ai+BjA_i+B_j 一定不是前 n 小的数。

核心代码 if(i * j >= n) break;

单调栈

从名字上就听的出来,单调栈中存放的数据应该是严格单调有序的,具有以下两个性质。

  1. 满足从栈顶到栈底的元素具有严格的单调递增或单调递减性;
  2. 满足栈的后进先出特性,即越靠近栈底的元素越早进栈。

单调栈也分为单调递增栈和单调递减栈。

  • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从小到大
  • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从大到小

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
stack<int> st;
for (遍历这个数组){
if (栈空 || 栈顶元素大于等于当前比较元素){
入栈;
}
else{
while (栈不为空 && 栈顶元素小于当前元素){
栈顶元素出栈;
更新结果;
}
当前数据入栈;
}
}

单调栈的维护

如何维护一个单调栈?出栈很简单,与普通栈相同,关键操作是入栈

具体进栈过程

  • 对于单调递增栈,若当前进栈元素为e,从栈顶开始遍历元素,把小于e或者等于e的元素弹出栈,直接遇到一个大于e的元素或者栈为空为止,然后再把e压入栈中。
  • 对于单调递减栈,则每次弹出的是大于e或者等于e的元素。

对于一个元素a,如果栈空则直接入栈。否则比较a与栈顶元素。假设一个单调递增的栈,若a > 栈顶元素,则直接把a入栈,栈仍满足单调的性质。若a < 栈顶元素,则将栈顶元素出栈,直到满足a < 栈顶元素,此时将a入栈。

例子

进栈元素分别为3,4,2,6,4,5,2,3

例题

同样,C++在实现时,我们也可以使用STL中的栈。

柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为[2,1,5,6,2,3][2,1,5,6,2,3]

图中阴影部分为所能勾勒出的最大矩形面积,其面积为1010 个单位。

思路:

  • 初看此题,第一个想到的就是暴力遍历。而暴力遍历又分两种情况,即 枚举宽 与 枚举高。
  • 枚举宽时,我们使用两重循环枚举矩形的左右边界以固定宽度 w ,时间复杂度为O(N2)O(N^2)
  • 枚举高时,我们可以使用一重循环枚举某一根柱子,将其固定为矩形的高度 h。随后我们从这跟柱子开始向两侧延伸,直到遇到高度小于 h 的柱子,就确定了矩形的左右边界。时间复杂度也为O(N2)O(N^2)
  • 很容易发现,枚举宽的做法已经使用了双重循环,很难再优化。所以我们通过对枚举高这一做法进行优化。

那么,该如何去寻找左右边界值呢?

这时,我们便可以使用单调栈进行优化。
在思路中,我们枚举高说向左右遍历寻找。未来降低时间复杂度,我们可以使用单调栈只向一边遍历。

当第i个柱子进栈时,如果栈顶的高度低于或等于第i个柱子,则第i个柱子进栈;
如果栈顶的高度高于第i个柱子,则出栈,并计算以柱子A为高的矩形最大面积。
同时,为防止越界问题,我们可以在左右两侧虚拟两根无限低的柱子,记高度为00

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int largestRectangleArea(int* heights, int heightsSize){
int top = -1;
int area, i;
int maxarea = 0;
int *stack = (int *)malloc(sizeof(int) * (heightsSize + 2));
int *buff = (int *)malloc(sizeof(int) * (heightsSize + 2));

buff[0] = 0;
for (int i = 1; i <= heightsSize; i++) {
buff[i] = heights[i - 1];
}
buff[heightsSize + 1] = 0;
stack[++top] = 0;
for (i = 1; i < heightsSize + 2; i++) {
while (top > 0 && buff[i] < buff[stack[top]]) {
area = (i - stack[top - 1] - 1) * buff[stack[top]];
maxarea = maxarea > area ? maxarea : area;
top--;
}
stack[++top] = i;
}
return maxarea;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n, n);

stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
right[mono_stack.top()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}

int ans = 0;
for (int i = 0; i < n; ++i) {
ans = ans > ((right[i] - left[i] - 1) * heights[i]) ? ans : ((right[i] - left[i] - 1) * heights[i]);
}
return ans;
}

单调队列

队列中元素之间的关系具有严格单调有序性,而且,队首和队尾都可以进行出队操作,只有队尾可以进行入队操作。因此,在单调队列中求最值十分容易。

单调队列与普通队列有些不同,因为右端既可以插入又可以删除,因此在代码中通常用一份数组和rearrearrearrear 两个指针来实现,而不是使用 STL 中的queuequeue。如果一定要使用 STL ,那么则可以使用双端队列(即两端都可以插入和删除),即dequedeque

队列的大小问题

在谈及单调栈时,无需关心栈的大小。而对于队列,队列的大小就很重要了。如果队列满了,我们的解决方法是,将队列头的元素弹出,再添加新的元素到队列尾。

单调队列的维护

具体入队过程

  • 对于单调递增队列,设当前准备入队的元素为e,从队尾开始把队列中的元素逐个与e对比,把比e大或者与e相等的元素逐个删除,直到遇到一个比e小的元素或者队列为空为止,然后把当前元素e插入到队尾。
  • 对于单调递减队列也是同样道理,只不过从队尾删除的是比e小或者与e相等的元素。

例子

队列大小不能超过3,入队元素依次为3,2,8,4,5,7,6,4

例题

滑动窗口

给定一个数列,从左至右输出每个长度为mm的数列段内的最小数和最大数。

Window positionMinimum valueMaximum value
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

数列长度:N<=106N <= 10^6m<=Nm<=N

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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e6+5;
int n, k, a[maxn];
int q[maxn];//队列,存的是下标
int main(){
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);

//维护最小值,序列要单调递增
int front = 1, rear = 0;
for(int i = 1; i <= n; ++i){
//如果如果尾部的在滑块之外,则删掉他们
while(front <= rear && q[front]+k <= i) ++front;
//如果头部的比当前的大,那么a[i]从头进去,队列就不递增了,所以删掉比a[i]大的头部
while(front <= rear && a[i] < a[q[rear]]) --rear;
q[++rear] = i;//头部插入i
if(i >= k) printf("%d ", a[q[front]]);//因为单调递增,所以答案在a的下标就是q[front]
}

//维护最大值,同上
putchar('\n');
memset(q,0,sizeof(q));
front = 1, rear = 0;
for(int i = 1; i <= n; ++i){
while(front <= rear && q[front]+k <= i) ++front;
while(front <= rear && a[i] > a[q[rear]]) --rear;
q[++rear] = i;
if(i >= k) printf("%d ", a[q[front]]);
}

return 0;
}

单调栈与单调队列

应用

单调队列

  1. 可以查询区间最值(不能维护区间k大,因为队列中很有可能没有k个元素)
  2. 优化DP
    单调队列一般是用于优化动态规划方面问题的一种特殊数据结构,且多数情况是与定长连续子区间问题相关联。

单调栈

  1. 左边区间第一个比它小的数,第一个比它大的数
  2. 确定这个元素是否是区间最值
  3. 右边区间第一个大于它的值
  4. 到 右边区间第一个大于它的值 的距离
  5. 确定以该元素为最值的最长区间

相同点

  1. 单调队列和单调栈的“头部”都是最先添加的元素,“尾部”都是最后添加的元素。
  2. 递增和递减的判断依据相同:从栈底(队尾)到栈顶(队首),元素大小的变化情况。所以队列和栈是相反的。
  3. 两者维护的时间复杂度都是O(n)O(n),每个元素都只操作一次。

不同点

  1. 单调队列可以从队列头弹出元素,可以方便地根据入队的时间顺序(访问的顺序)删除元素。
  2. 单调队列和单调栈维护的区间不同。当访问到第i个元素时,单调栈维护的区间为[0,i)[0, i),而单调队列维护的区间为(lastpop,i)(lastpop, i)
  3. 单调栈无法获取[0,i)[0, i)的区间最大值/最小值。因为单调队列可以访问“头部”和“尾部”,而单调栈只能访问栈顶(也就是“尾部”)。