今天我们选择的是codeforces contest 1417的C题k-Amazing Numbers。这是一道经典的数据结构题，全场通过4700+，比以往的C题要稍稍难一些。有一些trick，解法不算很难，但是不太容易想到。
题目链接：https://codeforces.com/contest/1417/problem/C
我们废话不多说了，直接来看题。
题意
给定n个数构成的数字，我们定义一个k-amazing数的概念。如果数a同时出现在数组中所有k个连续元素构成的序列当中，并且a是其中最小的那个，那么就称为a是一个k-amazing数字。
我们抽象一下，其实有两个条件，第一个条件是同时出现。我们假设数组是[1, 2, 3, 4, 5]，当k=3时，我们可以找到的序列是[1, 2, 3], [2, 3, 3], [3, 4, 5]。这三个序列当中的共有元素是3，并且只有3，所以3就是一个k-amazing数。第二个条件是最小，如果这样的数字可以找到多个，只有最小的那个数字才是k-amazing数。
现在给定数组a，要求所有的1-n的k-amazing数。
样例
首先输入一个整数t，表示测试数据组数()。
对于每组数据一共有三行输入，第一行输入为一个整数n()。
第二行输入n个整数。
要求输出一行整数，表示k=1到k=n时的所有k-amazing数，如果不存在则输出-1。
题解
这道题的题意倒是挺明确的，没什么含糊不清的情况。但是我们分析一下会发现，想要顺着题意去解决是不可能的。因为我们没有什么特别好的方法可以快速寻找多个集合当中的交集，并且查询到交集之后还需要分析交集当中的最小值。
也尝试过引入线段树或者是树状数组等数据结构，依然一无所获。最后能够解出来其实挺取巧的，是因为注意到了一个细节，这个细节就是元素的范围，题目当中给定的是。这和我们以往的题目都不太一样，一般来说都会给定一个具体的值作为范围，而不是给定一个变量。
如果有过一定算法题基础和经验的同学，注意到这个应该能想到桶排序或者是基数排序。如果我们保证所有的元素都小于数组的长度，那么我们可以用一种很取巧的方式来完成排序。
我们直接来看代码：
a = [4, 3, 2, 5, 1]
ret = []
base = [0 for _ in range(6)]
for i in a:
base[i] += 1
for i in range(6):
if base[i] > 0:
for j in range(base[i]):
ret.append(i)
a = [4, 3, 2, 5, 1]
ret = []
base = [0 for _ in range(6)]
for i in a:
base[i] += 1
for i in range(6):
if base[i] > 0:
for j in range(base[i]):
ret.append(i)这个算法的复杂度是，要比一般的排序算法更快，因为我们利用了下标的天然有序性。顺着这条线我想到了问题的关键，发现我们一开始的思路其实走入了误区。
思维误区与提示
这道题最大的trick就是我们对于算法的初印象，我一直在想一种方法可以快速地根据k求出k-amazing数。然后我发现情况非常复杂，并且涉及到集合的处理，比较麻烦。
这道题需要我们反其道而行之，并不是根据k去寻找k-amazing数，而是根据一个数在数组当中出现的分布，来判断它可以构成什么k-amazing。这也是为什么所有出现的数要小于n的原因，并不是说一定要小于n才有解，而是为了给我们一个思维提示。
我简单来解释一下这其中的原理，大家立刻就明白了，其实非常非常简单，有点像是魔术师用很简单的障眼法欺骗了我们的感觉。
我们假设上面这条线是题目给定的数组，我们假设其中某一个数m出现了3次，分别是a1, a2和a3。那么请问，如果m是一个k-amazing数，这个k应该至少是多大？
很简单，应该是，我们肉眼观察一下应该是a2-a1，那么我们画出来应该是这样的：
其实就是简单的区间覆盖问题，如果k小于这个值，那么a1到a2中间的部分一定无法满足。你可能还是会觉得有问题，不对啊，我们要找的是最小值，你怎么能知道这个m是不是最小的呢？
这个问题也非常简单，我们只需要按照顺序从小到大去寻找k，那么第一个找到的一定就是答案。想明白了之后有没有醍醐灌顶，有没有豁然开朗的感觉？是不是还有我居然想到了，又有一点觉得自己早就应该想到了的矛盾感？这也是做算法题的乐趣所在，所谓的难者不会，会者不难，体现得淋漓尽致。
不过还有一个小trick，有可能对于有些k我们找不到答案，但是它并不一定不存在。这也很好理解，我们假设找到了k=3时的答案是m，我们没有直接找到间隔是4的数，那么问题来了，m满不满足k=4呢？当然是满足的，因为小的间隔都能成立，大的间隔一定也可以。
最后，贴上代码：
from collections import defaultdict
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split(' ')))
# 我们要记录元素的出现位置，会有多个，所以要用map[int]list的结构
dt = defaultdict(list)
for i, v in enumerate(arr):
dt[v].append(i)
ret = [-1 for _ in range(n+2)]
for i in range(1, n+1):
if i not in dt:
continue
# 由于下标是0开始的，所以第一段区间长度是下标+1
tmp = dt[i][0] + 1
# 寻找元素i出现的最大间隔
for idx in range(1, len(dt[i])):
tmp = max(tmp, dt[i][idx] - dt[i][idx-1])
tmp = max(tmp, n - dt[i][-1])
# 如果这个长度的答案没有出现过，就赋值
if ret[tmp] == -1:
ret[tmp] = i
# 如果m是k-amazing数，那么它也是k+1-amazing数
for i in range(2, n+1):
if ret[i-1] == -1:
continue
if ret[i] == -1 or ret[i] > ret[i-1]:
ret[i] = ret[i-1]
print(' '.join(map(str, ret[1: n+1])))
from collections import defaultdict
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split(' ')))
# 我们要记录元素的出现位置，会有多个，所以要用map[int]list的结构
dt = defaultdict(list)
for i, v in enumerate(arr):
dt[v].append(i)
ret = [-1 for _ in range(n+2)]
for i in range(1, n+1):
if i not in dt:
continue
# 由于下标是0开始的，所以第一段区间长度是下标+1
tmp = dt[i][0] + 1
# 寻找元素i出现的最大间隔
for idx in range(1, len(dt[i])):
tmp = max(tmp, dt[i][idx] - dt[i][idx-1])
tmp = max(tmp, n - dt[i][-1])
# 如果这个长度的答案没有出现过，就赋值
if ret[tmp] == -1:
ret[tmp] = i
# 如果m是k-amazing数，那么它也是k+1-amazing数
for i in range(2, n+1):
if ret[i-1] == -1:
continue
if ret[i] == -1 or ret[i] > ret[i-1]:
ret[i] = ret[i-1]
print(' '.join(map(str, ret[1: n+1])))这题非常有趣，强烈建议大家都试着做一下。
- END -