数据结构 1013 欣赏书法题解

Rooobin edited 6 年，6 月前

1013 欣赏书法题解

需要维护一个双向队列

从左往右遍历作品编号依次加入队列中，包括了所有大师的作品即停止，然后队首元素不断出队直到某队首元素出队后会导致队列不再包含所有大师的作品，这时形成一个最短的基础队列。（易知，如果队首出队一些元素仍符合题意条件，那么队列一定变小）

在此基础上，继续从左往右遍历，将新的作品入队，每入队一次，队首元素不断出队直到不包含所有大师的作品，如此反复直到遍历完所有作品，每进行入队-出队操作后，更新队列的头尾对应的下标

由于始终从左往右遍历，那么一定得到的是队首下标最小的队列

如果还是难以理解，下面引入图解辅助

考虑例子

10 4
1 1 1 2 3 1 1 4 2 3

首先维护一个双向队列，用一个数组实现即可

记录全局答案$l=0,r=10$

从起始点开始向右遍历，加入到队列中，判断是否包含所有的大师作品

加入1

显然不满足，继续加入，直到

此时包含了所有的大师作品（即1，2，3，4均已在队列中），记录此时的左右端点$left=0，right=7$ $(right-left<r-l)$ 所以更新答案$l=0,r=7$

然后进行左端出队操作

最左端的1出队

检测，发现仍满足题意（包含所有大师的作品），$left=1$

继续左端出队(1, 1)，直到

如果2出队则不满足题意，所以停止，更新$left=3$ $(right-left<r-l)$更新答案$l=3,r=7$

然后继续右端入队（2入队）

再进行左端出队，只能左端的2出队，更新$left=4$ $(right-left==r-l)$输出 $l$ 最小的，所以不更新

继续右端入队(3)

再左端出队(3, 1)

$left=6,right=9(right-left<r-l)$

更新$l=6,r=9$

已经遍历了所有作品，算法结束，输出答案6 9

PS: 有些同学暴力枚举，显然是会超时的，而如上的可称为”滑动窗口”的算法，是线性的时间复杂度（大家可以自行查阅资料研究）

Past Versions

• #619 by Rooobin (2018-09-27 21:17:45).

Comments

jxtxzzw

6 年，6 月前

基本线性？我觉得就·是·线性的复杂度呀。

回复 1 0

Rooobin

6 年，6 月前

确实是线性的，发的时候不太确定XD

回复 0 0

Rooobin

6 年，6 月前

第一次发题解，有问题欢迎大家讨论～

回复 0 0