双端队列及应用

一、学习目标

1.双端队列的定义及C++ STL中deque的基本用法

2.单调队列的原理及应用场景（滑动窗口最值问题）（4月18日请假同学补课）

3.掌握双端队列BFS（0-1 BFS）解决边权为0/1的最短路问题

二、前置知识

1.队列（queue）和栈（stack）的特点和用法。

2.bfs求最短路原理。

三、双端队列的定义及C++ STL中deque的基本用法

（一）deque简介

deque是一个双向队列（double-ended queue），可以在队列的两端进行元素的插入和删除操作。

deque是C++STL（标准模板库）中的一种容器，可以用于存储各种类型的元素。

deque的特点是可以在队列的两端进行元素的操作，并且可以高效地在队列的任意位置进行元素的插入和删除操作。可以说deque几乎涵盖了queue（队列）、stack（堆栈）、vector（向量 ）等的全部用法，功能非常的强大。 使用deque时需要包括头文件：

#include<deque>

(二)deque的定义和初始化

定义 deque<数据类型>容器名

例

//deque的定义 
deque<int>d1; //定义一个储存数据类型为int的双端队列d1 
deque<double>d2; //定义一个储存数据类型为double的双端队列d2 
deque<string>d3; //定义一个储存数据类型为string的双端队列d3 
deque<结构体类型>d4; //定义一个储存数据类型为结构体类型的双端队列d4 
deque<int> d5[N]; //定义一个储存数据类型为int的双端队列数组d5 
deque<double>d6[N]; //定义一个储存数据类型为double的双端队列数组d6

(三)deque的成员函数

push_back()//在队列的尾部插入元素。
push_front()//在队列的头部插入元素。
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素。
back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器

insert()//在指定位置插入元素 
erase()//在指定位置删除元素

（四）练习

P2952 [USACO09OPEN] Cow Line S

P9422 [蓝桥杯 2023 国 B] 合并数列

二、单调队列的原理和应用场景

（一）单调队列的原理

单调队列是一种特殊的队列数据结构，用于 解决 一些与序列相关的问题。单调队列中的元素按照其值的大小有序排列，同时还满足队列的先进先出的性质。

单调队列的主要特点是，队列中的元素始终保持一个单调性，可以是递增或递减。这意味着，当有新的元素入队时，队列会自动进行调整，将不符合要求的元素删除。

单调队列的应用场景主要是解决滑动窗口相关的问题。 滑动窗口 是指在一个序列中，窗口以固定大小向右滑动，每次滑动一个位置。在每个滑动窗口中，需要对窗口中的元素进行一些操作。

使用单调队列可以在O(n)的时间复杂度内解决滑动窗口问题。具体的操作过程如下：

首先，将窗口的前k个元素依次入队；
与队列尾部的元素进行比较，将比当前元素小的元素从队列尾部依次出队，直到队列尾部的元素大于等于当前元素，或者队列为空；
判断队列的头部元素是否已经超出了滑动窗口的范围，如果超出了，则将队列头部元素出队；
将当前元素入队；
对每个滑动窗口，都可以通过队列的头部元素获取到当前窗口的最大（最小）值。

总之，单调队列是一种高效解决滑动窗口问题的数据结构，它可以在O(n)的时间复杂度内完成操作。同时，单调队列也有一些其他的应用场景，如求滑动窗口中的最小值、最大值等。

（二）应用场景

有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。

1.数组模拟单调队列：h为队头 t为队尾 初始时h=1,t=0,队列为空

//数组模拟
//维护窗口最小值
    int h=1,t=0;//清空队列
    for(int i=1;i<=n;i++){//枚举队列
        while(h<=t&&a[q[t]]>=a[i])t--;//队尾出队（队列不空且新元素更优）
        q[++t]=i;//新元素从队尾入队（队列内存储下标，方便判断队头是否滑出了窗口）
        if(q[h]<i-k+1)h++;//队头元素滑出窗口，从队头入队
        if(i>=k)cout<<a[q[h]]<<" ";//使用最值
    }

2.stl 实现

//维护滑动窗口最小值
    for(int i=1;i<=n;i++){                
        while(!q.empty()&&a[q.back()]>=a[i])q.pop_back();
        q.push_back(i); 
        if(q.front()<i-k+1)q.pop_front();
        if(i>=k)cout<<a[q.front()]<<" ";       
    }

（三）练习

洛谷--【公益B班】单调队列单调栈

三、双端队列BFS（0-1 BFS）解决边权为0/1的最短路问题

（一）双端队列 BFS 的原理

双端队列 BFS 是一种用于解决边权只有 0 和 1（或两种不同代价）的最短路径问题的算法。它结合了 BFS 和 Dijkstra 的思想，但比优先队列更高效。

（二）核心思想

• 当边权为 0 时，从该边到达的新节点与当前节点距离相同，应优先扩展（放入队首）
• 当边权为 1 时，从该边到达的新节点距离+1，应延后扩展（放入队尾）

这样可以保证队列中的节点始终按距离非递减顺序排列，第一次访问到某个节点时的距离就是最短距离。

（三）算法步骤

1. 初始化双端队列，将起点放入队首，距离数组 dist 初始化为无穷大
2. 当队列不为空时：
   • 弹出队首节点 u
   • 遍历 u 的所有邻接边 (u,v,w)：
     • 如果 dist[v] > dist[u] + w：
       • 更新 dist[v] = dist[u] + w
       • 如果 w == 0，将 v 放入队首；否则放入队尾

（四）例题

P4667 [BalticOI 2011] Switch the Lamp On (Day1)

题目描述

Casper 在一个 $N\times M$ 的电路板上设计电路。有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。有 $N\times M$ 个这样的元件，你想将其排列成 $N$ 行，每行 $M$ 个。 电源连接到板的左上角。灯连接到板的右下角。只有在电源和灯之间有一条电线连接的情况下，灯才会亮着。为了打开灯，任何数量的电路元件都可以转动 90°（两个方向）。

在上面的图片中，灯是关着的。如果从右往左数第二列的任何一个电路元件被旋转 90°，电源和灯都会连接，灯被打开。现在请你编写一个程序，求出最小需要旋转多少电路元件。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，表示电路板的尺寸。 在以下 $N$ 行中，每一行有 $M$ 个符号 \ 或 /，表示连接对应电路元件对角线的导线的方向。

输出格式

如果可以打开灯，那么输出只包含一个整数，表示最少转动电路元件的数量。

如果不可能打开灯，输出 NO SOLUTION。

解题思路：

1.该题类似走迷宫，搜索从入口到出口的操作代价最少的路径。所走路径必须是格点之间的对角线，如果对角格点是连通的即边权为0，如果对角格点是不通的即边权为1。

2.每个格点周围有4个对角格点，出界的不走，不能更优的不走，可走的分两类：连通的和不连通的，连通的一定比不连通的更优。因此，入队的格点具有两段性(0或1)，这就需要用双端队列来维护。更优的从队头入队，不优的从队尾入队，这就保证了更优的先出队，先扩展。

3.双端队列操作：队头出队，扩展：连通则从队头入队，不通则从队尾入队。

4.注意：每个格点可能入队多次，但只扩展一次，第一次出队时即该状态的最少代价，因此需要vis数组标记是否已扩展过，即是否已找到最小代价。

5.模拟：

vis[0]=1,dis[0]=1;其余的点vis[i]=0,dis[i]=正无穷。

①初始时0出队，可走到的点有1，边权为0，从队头入队，此时队列中有1。dis[1]=dis[0]+0<dis[1],dis[1]更新为0.

②队头元素1出队，标记vis[1]=1。从1出发能走到、不越界且没标记过的点有2、3、4（顺时针方向），2和4从队尾入队，3从队头进队。dis[2]=1，dis[4]=1，dis[3]=0。

③队头元素3出队，标记vis[3]=1。从3出发能走到、不越界且没标记过的点有5、6、7（顺时针方向），5、6从队头进队，7从队尾入队。dis[5]=0，dis[6]=0，dis[7]=1。

④队头元素6出队，标记vis[6]=1。从6出发能走到、不越界且没标记过的点只有8，8从队尾入队。dis[6]=dis[8]+1<dis[8]（正无穷）,更新dis[8]=1。

⑤队头元素5出队，标记vis[5]=1。从5出发能走到、不越界且没标记过的点有2、9、8。

dis[2]=dis[5]+1=dis[2]，因此走到2的最小代价没有变小，2无需入队；

dis[9]=dis[5]+1<dis[9]（正无穷），更新dis[9]=1,9从队尾入队。

dis[8]=dis[5]+1=dis[8]，走到8的最小代价没有变小，8无需入队。

思考：假设5和8之间可以联通，队列中的元素如何变化？

6.实现细节：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int> PII;
const int N=510;
int n,m;
char e[N][N];//格内斜边
int d[N][N];//操作步数
bool vis[N][N];//标记是否已找到最小代价
//es数组：一个格点与四周格点联通，那么四周格子的图形顺时针应该是\/\/,es数组记录这个状态，后面用来比对。
char es[]="\\/\\/";//斜边 左上角开始顺时针记录（转义字符\\表示'\'）;
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};//格点(1,1)的对角格点：(0,0),(0,2),(2,2),(2,0) 
int ex[]={-1,-1,0,0},ey[]={-1,0,0,-1};//格点(1,1)的四周格子:(0,0),(0,1),(1,0),(1,1)
deque<PII> q;
int bfs(){
    memset(d,0x3f,sizeof(d));
    d[0][0]=0;
    q.push_back({0,0});
    while(!q.empty()){
        PII u=q.front();
        q.pop_front();//队头出队
        int x=u.first,y=u.second;//当前格点坐标
        if(vis[x][y])continue;//已最小，跳过
        vis[x][y]=1;//出队标记，只一次
        for(int i=0;i<4;i++){
            int a=x+dx[i];//子格点
            int b=y+dy[i];
            if(a<0||a>n||b<0||b>m)continue;
            int ea=x+ex[i];//比对四周的格子图形
            int eb=y+ey[i];
            int dd=d[x][y]+(e[ea][eb]==es[i]?0:1);//计算新代价
            if(dd<d[a][b]){//从(x,y)到(a,b)代价更小
                d[a][b]=dd;
                if(e[ea][eb]!=es[i])q.push_back({a,b});//队尾入队
                else q.push_front({a,b});//队头入队
            }
        }

    }
    return d[n][m];//输出终点答案
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>e[i];
    }
    int dd=bfs();
    if(dd==0x3f3f3f3f)cout<<"NO SOLUTION";
    else cout<<dd;
    return 0;
}

（五）练习

洛谷：

P4667 [BalticOI 2011] Switch the Lamp On (Day1)

P1849 [USACO12MAR] Tractor S

P4554 小明的游戏