单调队列(Monotone queue)

~~首先,我们要知道什么是单调队列~~ ### 单调队列定理 ``` 单调递减（增）的队列 由于单调队列的队头每次一定最小值，故查询时间复杂度O(1) 每个元素最多进（出）队一次，故维护单调队列的时间复杂度仅为O(n) 单调队列入队时：会检查队尾元素是否仍然具备单调性，如果不具备则删除队尾元素，这个对队尾元素“出队”的操作和普通队列是不同的 注：在实际应用中，单调队列直接解题的可能性不大，取而代之的是单调队列基础上改进的斜率优化，虽然使用频率不高，但该结构仍需掌握，因为有许多算法建立在其基础上，且在一些程序中意义非凡 ``` ~~如果连着都不能理解的话,先去上课吧~~ 来玩笑，就算是你看不懂，也可以看看代码 来看看题目 ### 题目描述 ``` 给定一个长度为n（n<=1e6）的数组 有一个大小为k的滑动窗口从数组的最左端移动到最右端 你可以看到窗口中的k个数字 窗口每次向右滑动一个数字的距离 ``` 光是看是理解不了的，让我们来分析一下 从简单的看起，下面是一个例子： 数组是 [1 3 -1 -3 5 3 6 7]， 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 | 你的任务是得到滑动窗口在每个位置时的最大值和最小值。 ### 输入 ``` 输入包括两行 第一行包括n和k，分别表示数组的长度和窗口的大小（k＜n） 第二行包括n个数字 ``` ### 输出 ``` 输出包括两行 第一行包括窗口从左至右移动的每个位置的最小值 第二行包括窗口从左至右移动的每个位置的最大值 ``` ### 输入样例 ``` 8 3 1 3 -1 -3 5 3 6 7 ``` ### 输出样例 ``` -1 -3 -3 -3 3 3 3 3 5 5 6 7 ``` 首先,我们使用 **数组** 模拟,不涉及任何其他头文件 ``` #include <iostream> using namespace std; ``` 其次,我们使用 **队列储存数组元素下标** ，以判断 **以查看队首是否超时(是否超出移动窗口范围)** ~~终于上代码了~~ ``` #include <iostream> using namespace std; const int N = 1e6+10;// 最多1000000个元素 int q[N],h,t;// 单调队列 队首下标 队尾下标 int a[N],n,k;// 数组 元素个数 窗口下标 int main(){ // 读入 scanf("%d %d",&n,&k); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); // 清空队列 h = 1, t = 0; // 求滑动窗口最小 for(int i = 1; i <= n; i++){ // 队列不为空 队首元素是否超时 if(h <= t && q[h] < i-k+1) h++;// 如果队首元素超时 // 队列不为空 如果当前元素(a[i])<=队尾元素 while(h <= t && a[i] <= a[q[t]]) t--;// 维护单调性 // 元素入队 q[++t] = i; // 如果滑动窗口长度为3 if(i >= k) printf("%d ",a[q[h]]); // 输出 } printf("\n");// 换行 // 清空队列 h = 1, t = 0; // 求滑动窗口最大 for(int i = 1; i <= n; i++){ // 队列不为空 队首元素是否超时 if(h <= t && q[h] < i-k+1) h++;// 如果队首元素超时 // 队列不为空 如果当前元素(a[i])>=队尾元素 while(h <= t && a[i] >= a[q[t]]) t--;// 维护单调性 // 元素入队 q[++t] = i; // 如果滑动窗口长度为3 if(i >= k) printf("%d ",a[q[h]]); // 输出 } printf("\n");// 换行 return 0; } ```