题目提交地址
题目大意
给你
n
(
n
≤
3
∗
1
0
5
)
n(n\le3*10^5)
n(n≤3∗105)个数，每个数都
≤
n
\le n
≤n， 定义k-Amazing Numbers为大小为
k
k
k的滑窗遍历数组时，每次滑窗内的公共最小值，然后让输出k从1到n的所有k-Amazing Numbers
分析过程
这题的数字范围
≤
n
\le n
≤n，因此我们可以考虑从这里入手，枚举覆盖每个数字的最小滑窗大小。具体做法为：将每个数字对应的位置存下来，那么每个位置的最大间隔就是能够包含该数字的最小滑窗大小，我们定义
a
n
s
[
k
]
ans[k]
ans[k]表示大小为
k
k
k的滑窗中的答案，那么其实最后每个滑窗大小
k
k
k对应的答案就是其
a
n
s
[
k
]
ans[k]
ans[k]的最小前缀（大滑窗一定可以包含小滑窗）。
AC代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 3e5 + 100;
typedef long long ll
;
vector
<int> v
[maxn
];
int ans
[maxn
], a
[maxn
], n
;
int main(){
int t
, i
, j
;
ios
::sync_with_stdio(false);
cin
>>t
;
while(t
--){
cin
>>n
;
for(i
=1;i
<=n
;++i
) cin
>>a
[i
];
for(i
=1;i
<=n
;++i
){
v
[a
[i
]].push_back(i
);
}
for(i
=1;i
<=n
;++i
) ans
[i
] = 1e7;
for(i
=1;i
<=n
;++i
){
if(v
[i
].empty()) continue;
int tmp
= v
[i
][0];
for(j
=1;j
<v
[i
].size();++j
){
tmp
= max(tmp
, v
[i
][j
] - v
[i
][j
- 1]);
}
tmp
= max(tmp
, n
- v
[i
][j
- 1] + 1);
if(ans
[tmp
] == 1e7) ans
[tmp
] = i
;
}
for(i
=2;i
<=n
;++i
) ans
[i
] = min(ans
[i
- 1], ans
[i
]);
for(i
=1;i
<n
;++i
){
cout
<<(ans
[i
]!=1e7?ans
[i
]:-1)<<' ';
}
cout
<<(ans
[i
]!=1e7?ans
[i
]:-1)<<'\n';
for(i
=1;i
<=n
;++i
) v
[i
].clear();
}
return 0;
}
