1单调队列（Monotonic Queue）
21. 前提条件
3
4单调队列主要解决：滑动窗口最值问题
5
6典型题：
7
8239. 滑动窗口最大值（经典）
9
10例如：给一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
11
12返回 滑动窗口中的最大值 。
13
14nums = [1,3,-1,-3,5,3,6,7]
15
16k = 3
17
18窗口：
19
20[1 3 -1] -3 5 3 6 7
21
22最大：
23
243
25
26窗口：
27
281 [3 -1 -3] 5 3 6 7
29
30最大：
31
323
33
34窗口：
35
361 3 [-1 -3 5] 3 6 7
37
38最大：
39
405
41
42……
43
44输出：3 3 5 5 6 7
45
462. 为什么不能暴力？
47
48暴力：
49
50for(i)
51{
52 遍历窗口
53
54 找最大
55}
56
57复杂度：n*k
58
593. 核心思想
60
61队列里面保存当前窗口
62
63可能成为最大值的元素
64
65例如：
66
67窗口：
68
691
70
713
72
73来了：2
74
75那么：3比2大
76
77以后：2
78
79永远不可能成为最大值
80
81因为：3
82
83一直挡在它前面。
84
85所以：2
86
87不用删除。
88
89但是如果：
90
91来了：5
92
93那么：
94
955>2
96
975>3
98
995>1
100
101说明：
102
1031
104
1052
106
1073
108
109以后都不可能成为最大值。
110
111全部删掉。
112
113所以叫单调队列。
114
1154. 为什么叫单调？
116
117例如维护窗口最大值。
118
119队列从队头到队尾
120
121单调递减。
122
123例如：
124
1258
126
1276
128
1295
130
1312
132
133队头一定最大。
134
135所以答案永远：
136
137queue[front]
138
1395. 队列里面放什么？
140
141和单调栈一样。
142
143放下标不是值。
144
145因为窗口会移动。
146
147必须知道哪个元素已经出了窗口。
148
149例如：
150
151窗口：
152
153[1 3 -1]
154
155对应：
156
1570
158
1591
160
1612
162
163下一次：
164
165窗口：
166
167[3 -1 -3]
168
169下标：
170
1710：
172
173已经离开。
174
175必须删除。
176
177所以必须存下标。
178
1796. 固定模板
180for(int i=0;i<n;i++)
181{
182 //① 删除已经离开窗口
183 while(front<=rear &&
184 queue[front]<=i-k)
185 {
186 front++;
187 }
188
189 //② 保持单调递减
190 while(front<=rear &&
191 nums[queue[rear]]<=nums[i])
192 {
193 rear--;
194 }
195
196 //③ 当前元素入队
197 queue[++rear]=i;
198
199 //④ 窗口形成
200 if(i>=k-1)
201 {
202 ans[index++]=nums[queue[front]];
203 }
204}
205
206
207就是这个模板。
208
2097. C代码（239）
210int* maxSlidingWindow(int* nums,
211 int numsSize,
212 int k,
213 int* returnSize)
214{
215 int queue[100001];
216
217 int front=0;
218
219 int rear=-1;
220
221 int* ans=
222 malloc((numsSize-k+1)*sizeof(int));
223//窗口个数
224 int index=0;
225
226 for(int i=0;i<numsSize;i++)
227 {// 删除已经滑出当前窗口的下标（也就是超出窗口范围的元素删除和已经再无可能成为最大值的元素删除）
228 while(front<=rear &&
229 queue[front]<=i-k)
230 {
231 front++;
232 }
233// 删除队尾中比当前 nums[i] 小或相等的元素
234// 因为它们以后不可能成为最大值
235 while(front<=rear &&
236 nums[queue[rear]]<=nums[i])
237 {
238 rear--;
239 }
240// 当前下标 i 入队，作为候选最大值
241//queue数组不删元素，只是有效值的区间变了
242 queue[++rear]=i;
243// 从第一个完整窗口开始，每一轮输出队头对应的值
244 if(i>=k-1)
245 {
246 ans[index++]=
247 nums[queue[front]];
248 }
249 }
250
251 *returnSize=index;
252
253 return ans;
254}
2558. 举例
256
257数组：
258
2591 3 -1 -3 5 3 6 7
260
261窗口：
262
263k=3
264i=0
265
266来了：
267
2681
269
270队列：
271
272空。
273
274入队：
275
2761
277
278对应：
279
280下标：
281
2820
283i=1
284
285来了：
286
2873
288
289比较：
290
2913>1
292
293说明：
294
2951
296
297以后永远：
298
299不会成为最大值。
300
301弹：1
302
303然后3入队。
304
305队列：
306
3073
308
309对应：
3101
311
312i=2来了：-1
313
314比较：-1>3？
315
316不是。
317
318直接入队。
319
320得到：
321
3223
323
324-1
325
326窗口：形成最大队头
327
328=
329
3303
331
332输出：
333
3343
335i=3
336
337窗口：
338
339右移。
340
341现在：
342
343窗口：
344
3453
346
347-1
348
349-3
350
351先：
352
353检查：
354
355有没有：
356
357过期。
358
359队头：
360
3611
362
363对应：
364
3653
366
367没有：
368
369过期。
370
371然后：
372
373-3
374
375入队。
376
377得到：
378
3793
380
381-1
382
383-3
384
385最大：
386
387还是：
388
3893
390i=4
391
392来了：
393
3945
395
396首先：
397
398窗口：
399
400移动。
401
402队头：
403
4043
405
406已经：
407
408过期。
409
410删。
411
412然后：
413
414比较：
415
4165>-3
417
418弹
419
4205>-1
421
422弹
423
4245>3
425
426弹
427
428全部：
429
430弹掉。
431
432队列：
433
434空。
435
436最后：
437
4385：
439
440入队。
441
442得到：
443
4445
445
446以后：
447
448最大：
449
450一直：
451
4525。
453
4549. 为什么也是 while？
455
456例如：队列：
457
4588
459
4606
461
4624
463
4642
465
466来了10
467
468必须一直删。
469
47010>2删
47110>4删
47210>6删
47310>8删
474
475如果if只能删一个。
476
477所以必须while。
478
47910. 时间复杂度
480
481很多人：
482
483觉得：
484
485while
486
487是不是
488
489O(n²)?
490
491其实：
492
493不是。
494
495因为：
496
497每个元素：
498
499最多：
500
501入队一次
502
503出队一次
504
505所以：总共2n
506
507复杂度：O(n)
50811. 单调栈 单调队列
509单调栈 单调队列
510最近更大/更小 滑动窗口最值
511LIFO（后进先出） FIFO（先进先出）
512维护单调性 维护单调性
513保存下标 保存下标
514每个元素进出一次 每个元素进出一次
515O(n) O(n)
516
51712. 易错点
518① 队列存下标，不存值。
519
520② 先删过期元素，再维护单调性。
521
522③ while，不是if。
523
524④ 队头永远是当前窗口最大值。
525
526⑤ i>=k-1 才开始输出答案。
52713. 总结
528单调队列
529
530作用：滑动窗口最大/最小值
531
532--------------------------------
533
534维护：
535
536单调递减队列
537
538队头：
539
540永远最大
541
542--------------------------------
543
544步骤：
545
546① 删除窗口外元素
547
548② 删除队尾较小元素
549
550③ 当前元素入队
551
552④ 输出队头
553
554--------------------------------
555
556复杂度：
557
558O(n)
559
560因为：
561
562每个元素
563
564最多：
565
566进一次
567
568出一次。
569单调栈和单调队列的最终区别（一定要记住）
570
571
572
573单调栈：
574
575"我不知道右边什么时候会出现答案，所以先压栈等待。"
576
577↓
578
579用于：最近更大、最近更小。
580
581--------------------------------
582
583单调队列：
584
585"窗口一直在移动，我要维护当前窗口的最优元素。"
586
587↓
588
589用于：滑动窗口最大值、最小值。
单调队列（Monotonic Queue）
- 前提条件
单调队列主要解决：滑动窗口最值问题
典型题：
- 滑动窗口最大值（经典）
例如：给一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
nums = [1,3,-1,-3,5,3,6,7]
k = 3
窗口：
[1 3 -1] -3 5 3 6 7
最大：
3
窗口：
1 [3 -1 -3] 5 3 6 7
最大：
3
窗口：
1 3 [-1 -3 5] 3 6 7
最大：
5
……
输出：3 3 5 5 6 7
- 为什么不能暴力？
暴力：
for(i)
{
遍历窗口
找最大
}
复杂度：n*k
- 核心思想
队列里面保存当前窗口
可能成为最大值的元素
例如：
窗口：
1
3
来了：2
那么：3比2大
以后：2
永远不可能成为最大值
因为：3
一直挡在它前面。
所以：2
不用删除。
但是如果：
来了：5
那么：
5>2
5>3
5>1
说明：
1
2
3
以后都不可能成为最大值。
全部删掉。
所以叫单调队列。
- 为什么叫单调？
例如维护窗口最大值。
队列从队头到队尾
单调递减。
例如：
8
6
5
2
队头一定最大。
所以答案永远：
queue[front]
- 队列里面放什么？
和单调栈一样。
放下标不是值。
因为窗口会移动。
必须知道哪个元素已经出了窗口。
例如：
窗口：
[1 3 -1]
对应：
0
1
2
下一次：
窗口：
[3 -1 -3]
下标：
0：
已经离开。
必须删除。
所以必须存下标。
-
固定模板
for(int i=0;i<n;i++)
{
//① 删除已经离开窗口
while(front<=rear &&
queue[front]<=i-k)
{
front++;
}
//② 保持单调递减
while(front<=rear &&
nums[queue[rear]]<=nums[i])
{
rear--;
}
//③ 当前元素入队
queue[++rear]=i;
//④ 窗口形成
if(i>=k-1)
{
ans[index++]=nums[queue[front]];
}
}
就是这个模板。
-
C代码（239）
int* maxSlidingWindow(int* nums,
int numsSize,
int k,
int* returnSize)
{
int queue[100001];
int front=0;
int rear=-1;
int* ans=
malloc((numsSize-k+1)*sizeof(int));
//窗口个数
int index=0;
for(int i=0;i<numsSize;i++)
{// 删除已经滑出当前窗口的下标（也就是超出窗口范围的元素删除和已经再无可能成为最大值的元素删除）
while(front<=rear &&
queue[front]<=i-k)
{
front++;
}
// 删除队尾中比当前 nums[i] 小或相等的元素
// 因为它们以后不可能成为最大值
while(front<=rear &&
nums[queue[rear]]<=nums[i])
{
rear--;
}
// 当前下标 i 入队，作为候选最大值
//queue数组不删元素，只是有效值的区间变了
queue[++rear]=i;
// 从第一个完整窗口开始，每一轮输出队头对应的值
if(i>=k-1)
{
ans[index++]=
nums[queue[front]];
}
}
*returnSize=index;
return ans;
}
-
举例
数组：
1 3 -1 -3 5 3 6 7
窗口：
k=3
i=0
来了：
1
队列：
空。
入队：
1
对应：
下标：
0
i=1
来了：
3
比较：
3>1
说明：
1
以后永远：
不会成为最大值。
弹：1
然后3入队。
队列：
3
对应：
1
i=2来了：-1
比较：-1>3？
不是。
直接入队。
得到：
3
-1
窗口：形成最大队头
=
3
输出：
3
i=3
窗口：
右移。
现在：
窗口：
3
-1
-3
先：
检查：
有没有：
过期。
队头：
1
对应：
3
没有：
过期。
然后：
-3
入队。
得到：
3
-1
-3
最大：
还是：
3
i=4
来了：
5
首先：
窗口：
移动。
队头：
3
已经：
过期。
删。
然后：
比较：
5>-3
弹
5>-1
弹
5>3
弹
全部：
弹掉。
队列：
空。
最后：
5：
入队。
得到：
5
以后：
最大：
一直：
5。
- 为什么也是 while？
例如：队列：
8
6
4
2
来了10
必须一直删。
10>2删
10>4删
10>6删
10>8删
如果if只能删一个。
所以必须while。
- 时间复杂度
很多人：
觉得：
while
是不是
O(n²)?
其实：
不是。
因为：
每个元素：
最多：
入队一次
出队一次
所以：总共2n
复杂度：O(n)
11. 单调栈 单调队列
单调栈 单调队列
最近更大/更小 滑动窗口最值
LIFO（后进先出） FIFO（先进先出）
维护单调性 维护单调性
保存下标 保存下标
每个元素进出一次 每个元素进出一次
O(n) O(n)
- 易错点
① 队列存下标，不存值。
② 先删过期元素，再维护单调性。
③ while，不是if。
④ 队头永远是当前窗口最大值。
⑤ i>=k-1 才开始输出答案。
13. 总结
单调队列
作用：滑动窗口最大/最小值
维护：
单调递减队列
队头：
永远最大
步骤：
① 删除窗口外元素
② 删除队尾较小元素
③ 当前元素入队
④ 输出队头
复杂度：
O(n)
因为：
每个元素
最多：
进一次
出一次。
单调栈和单调队列的最终区别（一定要记住）
单调栈：
"我不知道右边什么时候会出现答案，所以先压栈等待。"
↓
用于：最近更大、最近更小。
单调队列：
"窗口一直在移动，我要维护当前窗口的最优元素。"
↓
用于：滑动窗口最大值、最小值。
