洛谷：P2032：扫描


洛谷：P2032：扫描

Table of Contents

题目

P2032：扫描

分析

这道题如果用暴力法，会十分耗时，时间复杂度在\(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

答案

Solution

思考

在某种程度上，这也是一个双指针的练习题。但如果用STL中的deque会更简便。

Previous Next