队列相关概念
队列中的数据存取方式是“先进先出”,只能向队尾插入数据,从队头移出数据.
队列的原型在生活中很常见,如食堂打饭的队伍,先到先服务.队列有两种实现方式:链队列和循环队列,如图1.2所示.
链队列可以看作单链表的一种特殊情况,用指针把各个节点连接起来.
循环队列是一种顺序表,使用一组连续的存储单元依次存放队列元素,用两个指针head和tail分别指示队头元素和队尾元素,当head和tail走到底时,下一步回到开始的位置,从而在这组连续空间内循环.
循环队列能解决溢出问题.如果不循环,head和tail都一直往前走,可能会走到存储空间之外,导致溢出.
队列和栈的主要问题是查找较慢，需要从头到尾一个个查找，在某些情况下可以用优先队列,让优先级最高(最大的数或最小的数)先出队列.
竞赛中一般用STLqueue或手写静态数组实现队列.
STL queue
STLqueue的主要操作如下:
(1)queue< Type >q: 定义队列,Type为数据类型,如int、float、char等.
(2)q.push(item): 把item放进队列.
(3)q.front(): 返回队首元素,但不会删除.
(4)q.pop(): 删除队首元素.
(5)q.back(): 返回队尾元素.
(6)q.size(): 返回元素个数.
(7)q.empty():检查队列是否为空.
例1.2 机器翻译
下面是STLqueue的代码,由于不用自己管理队列,代码很简洁.
注意检查内存中是否有单词的方法.如果一个一个地暴力搜索,太慢;如果用哈希算法,不仅很快,而且代码简单.
#include<bits/stdc++.h>
using namespace std;
int main() {
int m, n;
scanf("%d %d", &m, &n);
queue<int> mem;
int Hash[1003] = {0};
int cnt = 0;
while (n--)
{
int en;
scanf("%d", &en);
if (!Hash[en])
{
++cnt;
mem.push(en);
Hash[en] = 1;
while (mem.size() > m)
{
Hash[mem.front()] = 0;
mem.pop();
}
}
}
printf("%d\n", cnt);
return 0;
}
手写循环队列
下面是循环队列的手写模板.
代码中给出了静态分配空间和动态分配空间两种方式(动态分配实现放在注释中).
竞赛中一般用静态分配.
#include<bits/stdc++.h>
// 定义队列大小
#define N 1003
// 用哈希检查内存中有没有单词
int Hash[N]={0};
// 定义循环队列结构体
struct myqueue
{
int data[N];
// 如果动态分配，可以这样写: int * data;
int head;
int rear;
// 初始化队列
bool init()
{
// 如果动态分配，这样写: Q.data=(int*) malloc(N * sizeof(int));
data = new int[N];
if (!data)
return false;
head = rear = 0;
return true;
}
// 返回队列长度
int size()
{
return (rear - head + N) % N;//重点
}
// 判断队列是否为空
bool empty()
{
return size() == 0;
}
// 队尾插入新元素
bool push(int e)
{
if ((rear + 1) % N == head)
return false;
data[rear] = e;
rear = (rear + 1) % N;
return true;
}
// 删除队头元素，并返回它
bool pop(int &e)
{
if (head == rear)
return false;
e = data[head];
head = (head + 1) % N;//重点-循环链表的表征
return true;
}
// 返回队首，但不删除
int front() {
return data[head];
}
};
int main() {
Queue Q;
Q.init();
int m, n;
std::cin >> m >> n;
int cnt = 0;
while (n--) {
int en;
std::cin >> en;
if (!Hash[en])
{
// 如果内存中没有这个单词
++cnt;
Q.push(en);
Hash[en] = 1;
while (Q.size() > m) {
int tmp;
Q.pop(tmp);
Hash[tmp] = 0;
}
}
}
std::cout << cnt << std::endl;
return 0;
}
双端队列和单调队列
概念
前面的队列很“规矩”,队列的元素都是“先进先出”,队头只能弹出,队尾只能进入.
有没有不那么规矩的队列呢?
这就是双端队列:双端队列是一种具有队列和栈性质的数据结构,它能在两端进行插入和删除,而且也只能在两端插入和删除.
更可靠的编码可以用STL的双端队列deque,它的用法如下。
(1)dq[i]:返回队列中下标为i的元素。
(2)dq.front():返回队头。
(3)dq.back():返回队尾。
(4)dq.pop_back():删除队尾,不返回值。
(5)dq.pop_front():删除队头,不返回值。
(6)dq.push_back(e):在队尾添加一个元素e。
(7)dq.push_front(e):在队头添加一个元素e。
双端队列的经典应用是单调队列。
单调队列中的元素是单单调有序的,且元素在队列中的顺序和原来在序列中的顺序一致;单调队列的队头和队尾都能入队和出队。
提示：
灵活运用单调队列能够使很多问题的求解获得优化。
其原理可以简单地概括为:
序列中的几个元素,用单调队列处理时,每个元素只需要进出队列一次,复杂度为O(n)。
单调队列与滑动窗口
下面介绍单调队列的基本应用,了解如何通过单调队列获得优化。
注意队列中"删头、去尾、窗口"的操作。
例1.3 滑动窗口
本题用暴力法很容易编程:从头到尾扫描,每次检查处个数,一共检查O(nk)次。
暴力法显然会超时。
下面用单调队列求解,它的复杂度为O(n)。
在本题中,单调队列有以下特征：
(1)队头的元素始终是队列中最小的。根据需要输出队头,但是不一定弹出。
(2)元素只能从队尾进入队列,从队头、队尾都可以弹出。
(3)序列中的每个元素都必须进入队列。
例如,x进入队尾时,和原队尾y比较,如果x<=y,就从队尾弹出y;一直到弹出队尾所有比x大的元素,最后x进入队尾。这个入队操作保证了队头元素是队列中最小的。
单调队列的时间复杂度:每个元素最多入队一次、出队一次,且出入队时间都为O(1),
因此总时间为O(n)。
因为题中需要逐一处理所有几个数,所以O(n)已经是能达到的最优复杂度。
从以上过程可以看出,单调队列有两个重要操作:删头、去尾。
(1)删头:如果队头的元素脱离了窗口,这个元素就没用了,弹出它。
(2)去尾:如果新元素进队尾时,原队尾的存在破坏了队列的单调性,就弹出它。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int main() {
int n, m;
scanf("%d%d", &n, &m);
int a[N];
deque<int> q;
// 读取序列元素
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
// 输出每个窗口中的最小值
for (int i = 1; i <= n; i++)
{
// 去尾操作，保持队列中的元素对应的值单调递减
while (!q.empty() && a[q.back()] > a[i])
q.pop_back();
q.push_back(i);
if (i >= m)
{
// 输出当前窗口中的最小值
while (!q.empty() && q.front() <= i - m)
q.pop_front();
printf("%d ", a[q.front()]);
}
}
printf("\n");
// 清空队列，准备用于求最大值
while (!q.empty())
q.pop_front();
// 输出每个窗口中的最大值
for (int i = 1; i <= n; i++)
{
// 去尾操作，保持队列中的元素对应的值单调递增
while (!q.empty() && a[q.back()] < a[i])
q.pop_back();
q.push_back(i);
if (i >= m) {
// 输出当前窗口中的最大值
while (!q.empty() && q.front() <= i - m)
q.pop_front();
printf("%d ", a[q.front()]);
}
}
printf("\n");
return 0;
}
单调队列与最大子序和问题
首先说明什么是子序和：
给定长度为n的整数序列A,它的"子序列"定义为A中非空的一段连续的元素。
例如：
序列(6,-1,5,4,一7),前4个元素的子序和为6+(-1)+5+4=14。
最大子序和问题按子序列有无长度限制分为两种：
问题(1):不限制子序列的长度。
在所有可能的子序列中找到一个子序列,该子序列和最大。
问题(2):限制子序列的长度。
给定一个限制长度m,找出一段长度不超过m的连续子序列,使它的子序和最大。
问题(1)比较简单,用贪心法或动态规划(Dynamie Programming,DP)算法,复杂度都为O(n)。
问题(2)用单调队列,复杂度也为O(n)。通过这个例子,读者可以理解为什么单调队列能用于DP优化。
问题(1)不是本节的内容,不过为了参照,下面也给出是题解：
问题(1)的求解
用贪心法或DP,在O(n)时间内求解。下面是例题。
题解1: 贪心法
逐个扫描序列中的元素并累加。加一个正数时,子序和会增加;加一个负数时,子序和会减小。
如果当前得到的和变成了负数,这个负数在接下来的累加中会减少后面的求和,所以抛弃它,从下一位置开始重新求和。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
int main()
{
int t;
cin >> t;
// 处理每个测试用例
for (int i = 1; i <= t; i++)
{
int n;
cin >> n;
// 最大子序和，初始化为极小负数
int maxsum = -INF;
// 起点、终点、扫描位置
int start = 1, end = 1, p = 1;
int sum = 0;
// 遍历输入的序列
for (int j = 1; j <= n; j++)
{
int a;
cin >> a;
sum += a;
// 如果当前子序和大于最大子序和，更新最大子序和及起点和终点位置
if (sum > maxsum)
{
maxsum = sum;
start = p;
end = j;
}
// 如果当前子序和小于 0，从下一个位置重新开始求和
if (sum < 0)
{
sum = 0;
p = j + 1;
}
}
// 输出当前测试用例的结果
printf("Case %d:\n", i);
printf("%d %d %d\n", maxsum, start, end);
// 如果不是最后一个测试用例，输出一个空行
if (i!= t) cout << endl;
}
return 0;
}
题解2:动态规划
定义状态dp[i],表示以a[i]为结尾的最大子序和.
dp[i]的计算有两种情况:
(1)dp[i]只包括一个元素,就是a[i];
(2)dp[i]包括多个元素,从前面某个a[v]开始,v<i,到a[i]结束,即dp[i-1]+a[i]。
取两者的最大值,得到状态转移方程dp[i]=max(dp[i-1]+a[i]，a[i])。
在所有dp[i]中,最大值就是题目的解。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for (int k = 1; k <= t; k++)
{
int n;
cin >> n;
int dp[100005];
for (int i = 1; i <= n; i++)
{
cin >> dp[i];
}
//重点--------
int start = 1, end = 1, p = 1;
int maxsum = dp[1];
for (int i = 2; i <= n; i++)
{
// 状态转移方程：dp[i]=max(dp[i-1]+a[i], a[i])
if (dp[i - 1] + dp[i] >= dp[i])
{
dp[i] = dp[i - 1] + dp[i];
}
else
{
p = i;
}
if (dp[i] > maxsum)
{
maxsum = dp[i];
start = p;
end = i;
}
}
//重点--------
printf("Case %d:\n", k);
printf("%d %d %d\n", maxsum, start, end);
if (k!= t) cout << endl;
}
return 0;
}
