题目
分析
这道题如果用暴力法，会十分耗时，时间复杂度在\(O(N^2)\)。如果熟悉双指针，或者STL中的deque则会豁然开朗。
我们用样例数据模拟一下：
5 3
1 5 3 4 2
第一点，在5个数中从头到尾选择一个长度为3的窗口一共可以有三个：[1 5 3]、[5 3 4]、[3 4 2]。也就是总共有\(n-k+1\)个窗口。
第二点，输出应该是5 5 4。5在两个窗口中都是最大的，4在最后一个窗口最大。
详细过程如下：
第0步（i=0），当前元素num[0]=1。
| 步骤 | 操作 | dq | 窗口范围 | 最大值 |
|---|---|---|---|---|
| 移除不在窗口范围的元素 | 队列为空，无需移除。 | [] | [1] | - |
| 移除比当前元素小的元素 | 队列为空，无需移除。 | [] | [1] | - |
| 将当前元素加入队列 | 将索引 0 加入队列。 | [0] | [1] | - |
窗口未达到大小k |
不记录结果。 | [0] | [1] | - |
第1步（i=1），当前元素num[1]=5
| 步骤 | 操作 | dq | 窗口范围 | 最大值 |
|---|---|---|---|---|
| 移除不在窗口范围的元素 | 队列中索引0在窗口范围内，无需移除。 |
[0] | [1, 5] | - |
| 移除比当前元素小的元素 | nums[0] = 1小于nums[1] = 5，移除索引0。 |
[] | [1,5] | - |
| 将当前元素加入队列 | 将索引1加入队列。 |
[1] | [1, 5] | - |
窗口未达到大小k |
不记录结果。 | [1] | [1, 5] | - |
第2步（i=2），当前元素num[2]=3
| 步骤 | 操作 | dq | 窗口范围 | 最大值 |
|---|---|---|---|---|
| 移除不在窗口范围的元素 | 队列中索引1在窗口范围内，无需移除。 |
[1] | [1, 5, 3] | - |
| 移除比当前元素小的元素 | nums[1] = 5大于nums[2] = 3，不移除。 |
[1] | [1, 5, 3] | - |
| 将当前元素加入队列 | 将索引2加入队列。 |
[1, 2] | [1, 5, 3] | - |
窗口达到大小k |
记录结果。当前窗口最大一定是num[1]=5 |
[1, 2] | [1, 5, 3] | 5 |
第3步（i=3），当前元素num[3]=4
| 步骤 | 操作 | dq | 窗口范围 | 最大值 |
|---|---|---|---|---|
| 移除不在窗口范围的元素 | 队列中索引1在窗口范围内，无需移除。 |
[1, 2] | [5, 3, 4] | - |
| 移除比当前元素小的元素 | nums[2] = 3小于nums[3] = 4，移除。 |
[1] | [5, 3, 4] | - |
| 将当前元素加入队列 | 将索引3加入队列。 |
[1, 3] | [5, 3, 4] | - |
窗口达到大小k |
记录结果。当前窗口最大一定是num[1]=5 |
[1, 3] | [5, 3, 4] | 5 |
第4步（i=4），当前元素num[4]=2
| 步骤 | 操作 | dq | 窗口范围 | 最大值 |
|---|---|---|---|---|
| 移除不在窗口范围的元素 | 队列中索引1不在窗口范围内，需移除。 |
[3] | [3, 4, 2] | - |
| 移除比当前元素小的元素 | nums[3] = 4大于nums[4] = 2，不移除。 |
[3] | [3, 4, 2] | - |
| 将当前元素加入队列 | 将索引4加入队列。 |
[3, 4] | [3, 4, 2] | - |
窗口达到大小k |
记录结果。当前窗口最大一定是num[3]=4 |
[3, 4] | [3, 4, 2] | 4 |
答案
思考
在某种程度上，这也是一个双指针的练习题。但如果用STL中的deque会更简便。