ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【刷题条记】滑动窗口&单调队列标题 [打印本页]
作者: 来自云龙湖轮廓分明的月亮    时间: 2025-1-17 14:47
标题: 【刷题条记】滑动窗口&单调队列标题
【刷题条记】滑动窗口&单调队列标题

从前学的队列都很“规矩”。队列的元素都是“先辈先出”,队头只能弹出,队尾只能进入。有没有不那么“规矩”的队列呢?这就是双端队列。双端队列是一种具有队列和栈性质的数据结构。
它能在两头举行插入和删除,而且也只能在两头插入和删除。
最简朴的手写双端队列代码如下,使用时注意不能让队头和队尾溢出。
  1. const int N=1e5://队列大小,确保够用
  2. int que[Nl,head,tail;//队头队尾指针,队列大小为 tail-head+1
  3. head++;//弹出队头
  4. que!--headl= data;//数据 data入队头,注意不能溢出
  5. que.head;//读队头数据
  6. tai1--//弹走队尾
  7. que[++tail]= data;//数据data人队尾,注意不能溢出
复制代码
更可靠的编码可以用STL的双端队列deque,它的用法如下：
(1)dq:返回队列中下标为i的元素。
(2)dq.front():返回队头,
(3)dg.back():返回队尾。
(4)dq.pop_back():删除队尾,不返回值
(5)dq.pop_front():删除队头,不返回值。
(6)dq.push_back(e):在队尾添加一个元素 e。
(7)dq.push_front(e):在队头添加一个元素 e。
双端队列的经典应用是单调队列。单调队列中的元素是单调有序的,且元素在队列中的顺序和原来在序列中的顺序一致;单调队列的队头和队尾都能入队和出队。
滑动窗口 /【模板】单调队列

标题描述

有一个长为                                    n                              n                  n 的序列                                    a                              a                  a，以及一个大小为                                    k                              k                  k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列                                    [                         1                         ,                         3                         ,                         −                         1                         ,                         −                         3                         ,                         5                         ,                         3                         ,                         6                         ,                         7                         ]                              [1,3,-1,-3,5,3,6,7]                  [1,3,−1,−3,5,3,6,7] 以及                                    k                         =                         3                              k = 3                  k=3，有如下过程：
                                                                                                          窗口位置                                                                                             最小值                                                                                             最大值                                                                                                                   [1   3  -1] -3   5   3   6   7                                                                                                              −                                              1                                                                                                            3                                                                                                                    1  [3  -1  -3]  5   3   6   7                                                                                                              −                                              3                                                                                                            3                                                                                                                    1   3 [-1  -3   5]  3   6   7                                                                                                              −                                              3                                                                                                            5                                                                                                                    1   3  -1 [-3   5   3]  6   7                                                                                                              −                                              3                                                                                                            5                                                                                                                    1   3  -1  -3  [5   3   6]  7                                                                                              3                                                                                             6                                                                                                                    1   3  -1  -3   5  [3   6   7]                                                                                             3                                                                                             7                                                                                              \def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}                     窗口位置[1   3  -1] -3   5   3   6   7  1  [3  -1  -3]  5   3   6   7  1   3 [-1  -3   5]  3   6   7  1   3  -1 [-3   5   3]  6   7  1   3  -1  -3  [5   3   6]  7  1   3  -1  -3   5  [3   6   7]​最小值−1−3−3−333​最大值335567​​
输入格式

输入一共有两行，第一行有两个正整数                                    n                         ,                         k                              n,k                  n,k。
第二行                                    n                              n                  n 个整数，表示序列                                    a                              a                  a
输出格式

输出共两行，第一举动每次窗口滑动的最小值
第二举动每次窗口滑动的最大值
样例 #1

样例输入 #1

  1. 8 3
  2. 1 3 -1 -3 5 3 6 7
复制代码
样例输出 #1

  1. -1 -3 -3 -3 3 3
  2. 3 3 5 5 6 7
复制代码
提示

【数据范围】
对于                                    50                         %                              50\%                  50% 的数据，                                   1                         ≤                         n                         ≤                         1                                   0                            5                                       1 \le n \le 10^5                  1≤n≤105；
对于                                    100                         %                              100\%                  100% 的数据，                                   1                         ≤                         k                         ≤                         n                         ≤                         1                                   0                            6                                       1\le k \le n \le 10^6                  1≤k≤n≤106，                                             a                            i                                  ∈                         [                         −                                   2                            31                                  ,                                   2                            31                                  )                              a_i \in [-2^{31},2^{31})                  ai​∈[−231,231)。
solution

本题用暴力法很容易编程:从头至尾扫描,每次检査k个数,一共查抄 O(nk)次。暴力法显然会超时。下面用单调队列求解,它的复杂度为O(n)。
在本题中,单调队列有以下特征：
序列中的每个元素都必须进入队列。例如,进入队尾时,和原队尾y比力,如果x<y,就从队尾弹出 y;一直到弹出队尾所有比x大的元素,最后x进入队尾。这个人队操纵保证了队头元素是队列中最小的。
上述题解有点抽象,下面以食堂排队打饭为例说明它。
各人到食堂排队打饭时都有一个生理,在打饭之前先看看有什么菜,如果不好吃就走了。不过,能不能看到和身高有关,站在队尾的人如果个子高,眼光就能越过前面的人看到里面的菜;如果个子矮,会被挡住看不见。
一个矮个子来排队,他希望队伍前面的人都比他更矮。如果他会魔法,他来排队时,队尾比他高的人就自动从队尾离开,新的队尾如果仍比他高,也会离开:最后新来的矮个子成了新的队尾,而且是最高的。他终于能看到菜了,让人高兴的是,菜很好吃,以是他肯定不想走。
假设每个新来的人的魔法本领都比队列中的人更厉害,这个队伍就会酿成如许:每个新来的人都能排到队尾,但是都会被后面来的高个子赶走。如许一来,这个队列就会始终满意单调性:从队头到队尾，由矮到高，
但是,让这个魔法队伍郁闷的是,打饭阿姨一直忙本身的,顾不上打饭。以是排头的人等了一会儿,就走了,等待时间就是k。这有一个附带的现象:队伍长度不会凌驾k。输出是什么?每新来一个排队的人,排头如果还没走,他就向阿姨喊一声,这就是输出。以上是本题的实际模型。
下面举例描述算法流程,队列为(1,3,一1,-3,5,3,6,7),读者可以理解成身高。以输出最小值为例,表1.1中的“输出队首”就是本题的效果。
单调队列的时间复杂度:每个元素最多人队一次、出队一次,且出人队时间都为 O(1)因此总时间为 O(n)。因为题中必要逐一处理惩罚所有“个数,以是O(n)已经是能达到的最优复杂度。
从以上过程可以看出,单调队列有两个紧张操纵:删头、去尾。

下面写出代码，要重点关注删头、去尾的代码，他是要熟练把握的操纵：
  1. #include<bits/stdc++.h>
  2. #define N 1000003
  3. using namespace std;
  4. deque<int>que;
  5. int n,k;
  6. int a[N];
  7. int main(){
  8.     cin>>n>>k;
  9.     for(int i=1;i<=n;i++)cin>>a[i];
  11.     for(int i=1;i<=n;i++){
  12.         while(!que.empty()&&a[i]<a[que.back()])que.pop_back();  //“去尾”操作
  14.         que.push_back(i);
  16.         if(i>=k){
  17.             while(!que.empty()&&que.front()<=i-k)que.pop_front(); //”删头“操作
  18.             cout<<a[que.front()]<<" ";
  19.         }
  20.     }
  21.     cout<<endl;
  22.     while(!que.empty())que.pop_front();  //清空。再用一次
  24.         for(int i=1;i<=n;i++){
  25.         while(!que.empty()&&a[i]>a[que.back()])que.pop_back();
  27.         que.push_back(i);
  29.         if(i>=k){
  30.             while(!que.empty()&&que.front()<=i-k)que.pop_front();
  31.             cout<<a[que.front()]<<" ";
  32.         }
  33.     }
  34.    return 0;
  36. }
复制代码
下面再看一道题，他们之间有着细微的差别：
求m区间内的最小值

标题描述

一个含有                                    n                              n                  n 项的数列，求出每一项前的                                    m                              m                  m 个数到它这个区间内的最小值。若前面的数不足                                    m                              m                  m 项则从第                                    1                              1                  1 个数开始，若前面没有数则输出                                    0                              0                  0。
输入格式

第一行两个整数，分别表示                                    n                              n                  n，                                   m                              m                  m。
第二行，                                   n                              n                  n 个正整数，为所给定的数列                                              a                            i                                       a_i                  ai​。
输出格式

                                    n                              n                  n 行，每行一个整数，第                                    i                              i                  i 个数为序列中                                              a                            i                                       a_i                  ai​ 之前                                    m                              m                  m 个数的最小值。
样例 #1

样例输入 #1

  1. 6 2
  2. 7 8 1 4 3 2
复制代码
样例输出 #1

  1. 0
  2. 7
  3. 7
  4. 1
  5. 1
  6. 3
复制代码
提示

对于                                    100                         %                              100\%                  100% 的数据，保证                                    1                         ≤                         m                         ≤                         n                         ≤                         2                         ×                         1                                   0                            6                                       1\le m\le n\le2\times10^6                  1≤m≤n≤2×106，                                   1                         ≤                                   a                            i                                  ≤                         3                         ×                         1                                   0                            7                                       1\le a_i\le3\times10^7                  1≤ai​≤3×107。
乍一看好像是一回事？
我们分析一下样例，就知道事变不简朴。

我们可以看出来，最后一个数不在滑动窗口范围内！
那么对于前面的数不足                                    m                              m                  m 项怎么办呢？很简朴，那时侯单调队列仍在维护，以是直接输出队头即可！
看代码，注意差别：
  1. #include<bits/stdc++.h>
  2. #define N 2000003
  3. using namespace std;
  5. int n,m;
  6. int arr[N];
  7. deque<int>que;
  8. int main (){
  9.     cin>>n>>m;
  11.     for(int i=1;i<=n;i++)cin>>arr[i];
  12.     cout<<0<<endl;
  13.     for(int i=1;i<n;i++){ //注意此处i<n
  14.         while(!que.empty()&&arr[i]<arr[que.back()])que.pop_back();
  16.         que.push_back(i);
  17.         if(i>=m){
  18.         while(!que.empty()&&que.front()<=i-m)que.pop_front();
  20.         }
  21.         cout<<arr[que.front()]<<endl;//打印队头的位置在if之外
  23.     }
  25. return 0;
  27. }
复制代码
双倍经验，一道水题，跟模板题一个样。
扫描

标题描述

有一个                                    1                         ×                         n                              1 \times n                  1×n 的矩阵，有                                    n                              n                  n 个整数。
现在给你一个可以盖住一连                                    k                              k                  k 个数的木板。
一开始木板盖住了矩阵的第                                    1                         ∼                         k                              1 \sim k                  1∼k 个数，每次将木板向右移动一个单位，直到右端与第                                    n                              n                  n 个数重合。
每次移动前输出被覆盖住的数字中最大的数是多少。
输入格式

第一行两个整数                                    n                         ,                         k                              n,k                  n,k，表示共有                                    n                              n                  n 个数，木板可以盖住                                    k                              k                  k 个数。
第二行                                    n                              n                  n 个整数，表示矩阵中的元素。
输出格式

共                                    n                         −                         k                         +                         1                              n - k + 1                  n−k+1 行，每行一个整数。
第                                    i                              i                  i 行表示第                                    i                         ∼                         i                         +                         k                         −                         1                              i \sim i + k - 1                  i∼i+k−1 个数中最大值是多少。
样例 #1

样例输入 #1

  1. 5 3
  2. 1 5 3 4 2
复制代码
样例输出 #1

  1. 5
  2. 5
  3. 4
复制代码
提示

对于                                    20                         %                              20\%                  20% 的数据，                                   1                         ≤                         k                         ≤                         n                         ≤                         1                                   0                            3                                       1 \leq k \leq n \leq 10^3                  1≤k≤n≤103。
对于                                    50                         %                              50\%                  50% 的数据，                                   1                         ≤                         k                         ≤                         n                         ≤                         1                                   0                            4                                       1 \leq k \leq n \leq 10^4                  1≤k≤n≤104。
对于                                    100                         %                              100\%                  100% 的数据，                                   1                         ≤                         k                         ≤                         n                         ≤                         2                         ×                         1                                   0                            6                                       1 \leq k \leq n \leq 2 \times 10^6                  1≤k≤n≤2×106，矩阵中的元素大小不凌驾                                    1                                   0                            4                                       10^4                  104 并且均为正整数。
滑动窗口最大值：
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 2000005
  5. int arr[N];
  6. deque<int>que;
  7. int n,k;
  9. int main(){
  10.     cin>>n>>k;
  11.     for(int i=1;i<=n;i++)cin>>arr[i];
  13.     for(int i=1;i<=n;i++){
  14.         while(!que.empty()&&arr[i]>arr[que.back()])que.pop_back();
  16.         que.push_back(i);
  18.         if(i>=k){
  19.             while(!que.empty()&&que.front()<=i-k)que.pop_front();
  20.             cout<<arr[que.front()]<<endl;
  21.         }
  22.     }
  23.     return 0;
  24. }
复制代码
本文对于单调队列的解释参考了罗勇军，郭卫斌老师的《算法竞赛》。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4