0.总结

• Get to the points first. The article comes from LawsonAbs!
• 单调队列的含义
• 如何用单调队列解决实际问题
• 单调队列常见的例题
• 在for循环中实现当前窗口的最值判断
• 队首如果不是合理的结果，那么就应该进行出队【队首】操作。（但是这里就是单纯的弹出操作）
• 队尾如果不是更优的结果，则需要在某条件【通常是窗口长度内+满足大小特定关系】弹出队尾，然后将当前元素添加进去
• 上述两个步骤的顺序不是固定的，可以颠倒，主要是取决于题目的需要

1.题目

结合实际题目讲解单调队列，题目见上链接。

2.题意

计算该数的前m个数中的最小值，如果不足m个，则从第一个算起；如果前没有数，则输出0。

3.主要思想

3.1 单调队列

关于单调队列要说的有很多，我太菜了（我可能就是那个因为年龄太大而技能太差不会被放入到队列中的蒟蒻。。。o(╥﹏╥)o），自己理解这个概念花了很长时间，因为我自己一直很郁闷， 为啥队首的元素就是最优解？后来明白了，因为一直在对队尾元素进行某种维护操作（就使得当前的队首在满足某种前提下就是最优解，这个前提一般就是题目中限制的区间长度）。

需要注意的点有：

• 单调队列（是个算法概念）需要使用双端队列（是种数据结构）来实现，或者使用一个数组（标记左右端）来实现。
• 单调队列的重点其实就是根据某种原则（这种原则一般就是根据最优解确定的）维护队首和队尾。

下面是几篇有关单调队列的文章，讲的还行，供大家参考。

• AcWing单调队列讲义
• acWing例题最大子序和
• 最大子序和（单调队列算法）
• （络谷日报）单调队列

4.AC代码

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxN = 2000005;				 
int arr[maxN];

deque<int> que;//用于存储前m个数中的最小值
 
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 0;i< n;i++){
		scanf("%d",&arr[i]);
	}
	que.push_back(0);//将第一个数的下标 放到队列中 
	
	int temp ;		
	cout << 0<<"\n";
	que.push_back(0);//将下标0 放到队列中 		
	for(int i = 1;i< n;i++){ 				 
		temp = que.front();//取队首
				
		/*1.从队首取出最优解
			当然取出队首是有条件的，当前的最小值要在区间m内，否则需要将队首
			循环出队，找到的第一个队首才是最优解
			（可能有人要问，为什么第一个即队首元素就是最优解呢？）程序不能孤立的看，
			这是因为step3的操作，才能保证队首一定是最优解。 
		*/
		while(i - temp > m){//此时需要一直出队 
			que.pop_front();//队首出队 
			temp = que.front(); 			 
		}
		
		/*step2 :这里得到最优解的方式很简单，就是单纯的将其输出即可。		
		*/
		cout << arr[temp]<<"\n";
		temp = que.back();
		
		
		/*step 3: 对队尾进行维护操作，正是为了以后成为“队首”（因为队首一直在做删除
		操作，所以队尾终有一天会成为队首）而做准备 。 
		01.如果当前的元素比队尾还要小【arr[temp] >=arr[i]】，而且区间长度在m内【temp > i-m】，当然 
		这么做的前提是队里有元素【!que.empty()】，那么就要循环从队尾【重点】出队，
		直到出现某个数不满足上述的三个条件之一，就停止。
		02.然后再把该下标插入到队列中。 		
		*/ 
		while(!que.empty() && arr[temp] >= arr[i] && temp >i-m){
			que.pop_back();//队尾出队
			temp = que.back();
		}
		//while运行完之后，说明队列中的元素是单调增的！ 
		que.push_back(i);//入队i;  
	}cout<<"\n";		
}

4. 测试用例

6 2
7 8 1 4 3 2

8 4
1 7 8 9 1 0 3 2

5.更多

还有很多题目可以使用单调队列来做，这里列举一些：

• 【洛谷】 P1886 滑动窗口 /【模板】单调队列
  稍微改变的是，这题是包含自身节点的窗口，而案例分析中是求前m个窗口中的最值，但其实都是相似的。稍微修改一下代码的顺序就可以了。这里给出可AC的代码【都到这里了，可以点赞外加送波关注嘛｡◕ᴗ◕｡】

#include<iostream>
#include<deque>
using namespace std;
const int N = 1e6+5;
const int INF= 0x3f3f3f3f;
deque<int> deq;//使用一个双端队列 =>求区间内的最大值 
deque<int> que;//使用一个双端队列=> 求区间内的最小值 
int arr[N];//存储原数据
int maxV[N],minV[N],cnt=0;//存储输出结果 ;cnt表示个数 

int main(){
	int n,k;
	cin >> n >> k;
	for(int i = 0;i< n;i++){
		cin >> arr[i];
	}		
	deq.push_back(0);//最大值下标入队 
	que.push_back(0); //最小值 
	int top1,rear1,top2,rear2;//最小值队首，队尾 ； 最大值队首队尾 
	//输入下标i前k位数的最大最小值 
	for(int i = 0;i<n;i++){				
		/*=========求最小值================== 
		step1.将当前的元素判断是否需要入队，并且要选择一个合适的地方入队，需要满足的前提是： 
		01.队列非空
		02.当前的元素不比队尾大 
		03.在窗口k内的之前的“最小值”都得退掉 
		*/
		rear1 = que.back();//取队尾 
		while(!que.empty() && arr[i] <= arr[rear1] && (i-rear1)<k){
			que.pop_back();//队尾出队
			if(!que.empty()) 
				rear1 = que.back(); 
		} 
		que.push_back(i);//放入队尾 
		
		top1 = que.front();//取队首 
		//step2.找出合理的最值元素 
		while(i - top1 >= k){//如果已经超出区间的范围了-> 队首出队，再取队首 
			que.pop_front();
			top1 = que.front();
		} 		
		//step2.对最值元素进行操作 => 这里就是输出 
		if(i>=k-1)
			minV[cnt] = arr[top1];//输出元素	
				
		/*=========求最大值================== */ 
		rear2 = deq.back();//取队尾 
		while(!deq.empty() && arr[i] >= arr[rear2] && (i-rear2)<k){
			deq.pop_back();//队尾出队
			if(!deq.empty())
				rear2 = deq.back(); 
		} 
		deq.push_back(i);//放入队尾 	
		top2 = deq.front();//取队首 				
		while(i - top2 >= k){//如果已经超出区间的范围了-> 队首出队，再取队首 
			deq.pop_front();
			top2 = deq.front();
		}
		if(i>=k-1){
			maxV[cnt] = arr[top2];
			cnt++;
		}		
	}
	//输出下标i前k位数的最大最小值 	
	for(int i = 0;i<cnt;i++){
		cout << minV[i]<<" ";
	}cout <<"\n";
	for(int i = 0;i<cnt;i++){
		cout << maxV[i]<<" ";
	}cout <<"\n";
}

测试用例：

8 1
1 -1 1 -3 5 3 6 7

8 3
1 3 -1 -3 5 3 6 7

8 2
1 3 -1 -3 5 3 6 7

题目二

下面再结合LeetCode的一道题来看一下。

2.1 题目

2.2 分析

昨晚（20220903）写这道题的时候，一度认为要用单调栈写。但是如果是单调栈的话，那么就无法“两头操作”了。这里的两头操作指的就是既要输入又要删除。所以最合适的数据结构就是队列了。队列来了一个新数就要让这个数在有效的区间里最大。队列输出的时候，就要保证这个数在有效的区间内。

2.3 代码

同时需要注意的是：queue 库在python中的使用。
申请一个对象： que = Queue()
删除队列中的最后一个元素：del que.queue[-1]
删除队头并返回队头值：que.get()
这些操作比较重要，需要熟练运用。

from queue import Queue
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = Queue() # 得到一个队列
        # if len(nums) == 0:
        #     return []
        # elif len(nums) == 1:
        #     return nums
        res = []
        que.put(0)
        for i in range(0,len(nums)):
            rear = que.queue[-1] # 得到队尾
            while(que.qsize() and nums[i] >= nums[rear] and i - rear < k):
                del que.queue[-1]
                if que.qsize():
                    rear = que.queue[-1]
            
            # 将当前的这个数放到queue中
            que.put(i)

            # 找到合适的头，然后开始放入
            front = que.queue[0]
            while(i-front >=k ):
                que.get()
                front = que.queue[0] # 再取队头
            if i >= k-1:
                res.append(nums[front])
        #print(res)
        return res

# s = Solution()

# nums = [1,-1]
# k = 1
# s.maxSlidingWindow(nums = nums,k = k)