2903 窗口内不同元素
大约 2 分钟
2903 窗口内不同元素
【算法】 滑动窗口、计数
【C++】 滑动窗口、cnt数组、哈希表(unordered_map)
【难度】 入门
一、题目简述
给定 个整数,求所有长度为 的连续子数组中,不同元素个数的最大值。
数据范围:,元素值 的范围可能较大(或为负数),也可能较小(如 )。
二、解题思路
本题依然是定长滑动窗口,但统计的不是"和",而是"不同元素个数"。
核心问题:如何高效维护窗口内的不同元素个数?
- 维护一个计数表
cnt[x]记录窗口内每个数 的出现次数 - 维护一个变量
distinct记录当前不同元素的个数
窗口右移时:
- 新元素 进入窗口:
cnt[a[i]]++,如果计数从 0 变成 1,说明新增了一种元素,distinct++ - 旧元素 离开窗口:
cnt[a[i-k]]--,如果计数从 1 变成 0,说明这种元素在窗口内消失了,distinct-- - 更新答案
ans = max(ans, distinct)
计数表用什么数据结构?
- 如果 范围较小(如 或 ),用静态数组
int cnt[MAXV],访问 ,最快。 - 如果 范围很大或为负数,用
unordered_map<int, int>,平均 。
下面代码给出 unordered_map 版本,更通用。
手动模拟 [1, 2, 1, 3, 2, 4, 5],k=3:
| 步骤 | i | 窗口元素 | 进入 | 离开 | cnt 变化 | distinct | ans |
|---|---|---|---|---|---|---|---|
| i=1 | 1 | a₁=1 | — | cnt[1]:0→1 | 1 | — | |
| i=2 | 2 | a₂=2 | — | cnt[2]:0→1 | 2 | — | |
| i=3 | 3 | a₃=1 | — | cnt[1]:1→2 | 2 | 2 | |
| i=4 | 4 | a₄=3 | a₁=1 | cnt[3]:0→1; cnt[1]:2→1 | 3 | 3 | |
| i=5 | 5 | a₅=2 | a₂=2 | cnt[2]:1→2; cnt[2]:2→1 | 3 | 3 | |
| i=6 | 6 | a₆=4 | a₃=1 | cnt[4]:0→1; cnt[1]:1→0 | 3 | 3 | |
| i=7 | 7 | a₇=5 | a₄=3 | cnt[5]:0→1; cnt[3]:1→0 | 3 | 3 |
最大值 = 3。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
unordered_map<int, int> cnt;
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int distinct = 0, ans = 0;
for (int i = 1; i <= n; i++) {
// 新元素进入窗口
if (cnt[a[i]] == 0) distinct++;
cnt[a[i]]++;
// 旧元素离开窗口
if (i > k) {
cnt[a[i - k]]--;
if (cnt[a[i - k]] == 0) distinct--;
}
// 窗口大小达到 k 时更新答案
if (i >= k) ans = max(ans, distinct);
}
cout << ans << endl;
return 0;
}补充说明:如果题目明确元素值范围 ,可以将 unordered_map 替换为静态数组 int cnt[100005](记得初始化为 0),效率更高。
四、复杂度分析
- 时间复杂度:,每个元素进出窗口各一次,哈希表操作为 平均。
- 空间复杂度:,哈希表最坏存储所有不同元素;使用静态数组则为 。
