洛谷P1886 滑动窗口_bv1h5411j7o6

使用单调队列解题，队列里存储的是下标。我是看https://www.bilibili.com/video/BV1H5411j7o6我是看这个视频想清楚单调队列是怎么用的，写这个文章来保存一下我的思路和解题过程

利用递减队列找窗口最大值，队头保存的是最大值
利用递增队列找窗口最小值，队头保存的是最小值

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
	int n,k;
	vector<int> v,ansBig,ansLittle;
	deque<int> q;	//双向队列
	
	//输入n、k和序列a
	cin>>n>>k;
	while(n--){
		int t;
		
		cin>>t;
		v.push_back(t);
	}
	
	//找大的，此为递减队列
	for(int i=0;i<v.size();i++){
		//这里是为了使窗口滑过去后，不在这个窗口范围里的最大值弹出队列
		if(!q.empty() && i-q.front()>=k)
			q.pop_front();
		
		//正常的单调队列过程
		if(q.empty() || v[q.back()]>v[i]){
			q.push_back(i);
		}
		else{
			while(!q.empty() && v[q.back()]<=v[i]){
				q.pop_back();
			}
			q.push_back(i);
		}
		
		//因为队列是从序列a的第1个数开始入栈的，而窗口一开始是从框着前k个数开始的，所以		
		//要到前k个数都经历过一遍这个单调队列过程后，在把队头的最大值放入最大值答案数组里
		if(i>k){
			ansBig.push_back(v[q.front()]);
		}
	}
	
	//找小的，此为递增队列
	q.clear();	//清空队列
	for(int i=0;i<v.size();i++){
		//这里是为了使窗口滑过去后，不在这个窗口范围里的最小值弹出队列
		if(!q.empty() && i-q.front()>=k)
			q.pop_front();
		
		//正常的单调队列过程
		if(q.empty() || v[q.back()]<=v[i]){
			q.push_back(i);
		}
		else{
			while(!q.empty() && v[q.back()]>v[i]){
				q.pop_back();
			}
			q.push_back(i);
		}
		
		//同理
		if(i>k){
			ansLittle.push_back(v[q.front()]);
		}
	} 
	
	//输出窗口里最小的数
	for(int i=0;i<ansLittle.size();i++){
		cout<<ansLittle[i]<<" ";
	}
	
	cout<<endl;
	
	//输出窗口中最大的数
	for(int i=0;i<ansBig.size();i++){
		cout<<ansBig[i]<<" ";
	}
	
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

想要了解单调栈的话，也可以看看这篇文章，这篇文章里前面的介绍和伪代码个人认为很好，帮了我很大的忙。