-
复杂度分析
本题要求在长度为 N 的序列中, 求出所有长度为 M 的连续子区间的 mex 值的最小值.
根据题意, 数据规模达到了 N, M <= 2000000.常规的"滑动窗口结合平衡树或权值树状数组"解法, 其时间复杂度为
. 在极大的常数开销与 2 秒的严格时限下, 这种做法存在较高的超时 (TLE) 风险.
因此, 寻求一种纯线性
的解法是更为稳妥的选择.
-
核心算法:
最大间隔判定我们可以从"最终结果"出发进行逆向推导.
假设最终求得的最小 mex 值为 x, 这意味着具备以下两个推论:必定存在至少一个长度为 M 的区间, 其内部不包含数字 x.对于所有严格小于 x 的非负整数 (即 0 到 x-1), 它们必须在每一个长度为 M 的区间内都出现过.
为了判断某个数字 y 是否在所有长度为 M 的区间中均存在, 我们可以考察该数字在原数组中相邻两次出现位置的最大间隔 (Maximum Gap).
若数字 y 的最大间隔 <= M, 则任何长度为 M 的窗口在滑动时, 都必然会覆盖到至少一个 y.若数字 y 的最大间隔 > M, 则说明原数组中存在一段长度大于 M 的连续区间不包含 y.
我们完全可以将滑动窗口置于该区间内, 从而使得窗口内缺失数字 y.基于此结论, 我们只需从 0 开始, 依次递增检查每个自然数的最大间隔. 遇到的首个满足"最大间隔 > M"的自然数, 即为我们要寻找的最小 mex 值.
-
算法实现步骤设定边界:
为便于计算首末两端的间隔, 引入虚拟的起始位置 -1 与结束位置 N.
控制值域: 窗口长度最大为 N, 因此 mex 的结果不可能超过 N+1.
我们仅需开辟大小为 N+2 的数组记录位置信息, 超出此范围的数值对答案无影响.
遍历更新: 单次遍历输入数组, 使用 last_pos 记录每个有效数字上一次出现的位置, 并同步动态更新 max_gap 数组.
末端处理: 遍历完成后, 补充计算各数字最后一次出现位置至数组末端边界 N 的间隔.输出结果: 从 0 开始顺序遍历 max_gap 数组, 输出首个满足 max_gap[i] > M 的索引 i.
4.参考代码C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
void solve()
{
int n, m;
cin >> n >> m;
// 记录数字上一次出现的位置, 初始边界统一设定为 -1
vector<int> last_pos(n + 2, -1);
// 记录数字相邻出现的最大间隔
vector<int> max_gap(n + 2, 0);
for(int i = 0; i < n; i++)
{
int val;
cin >> val;
// 仅处理可能成为最终 mex 值的有效数据 (<= n+1)
if(val <= n + 1)
{
max_gap[val] = max(max_gap[val], i - last_pos[val]);
last_pos[val] = i;
}
}
// 从 0 开始逐一验证自然数
for(int i = 0; i <= n + 1; i++)
{
// 补充计算至数组末尾边界 n 的距离
max_gap[i] = max(max_gap[i], n - last_pos[i]);
// 寻找首个最大间隔超过窗口长度 m 的数字
if(max_gap[i] > m)
{
cout << i << endl;
return;
}
}
}
signed main(){
// 优化标准输入输出流的性能
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
- 复杂度总结时间复杂度:
京公网安备 11010502036488号