算法

(用map差分更新) $O(N\log N)$

可以用 std::map 来维护每种颜色出现的次数，并用变量 now 来记录当前区间出现的颜色个数，然后取最大的 now 即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::map;
using std::vector;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> c(n);
    rep(i, n) cin >> c[i];

    int ans = 0;
    map<int, int> mp;
    int now = 0;
    rep(i, n) {
        if (mp[c[i]] == 0) now++;
        mp[c[i]]++;
        if (i >= k) {
            mp[c[i - k]]--;
            if (mp[c[i - k]] == 0) now--;
        }
        ans = max(ans, now);
    }

    cout << ans << '\n';

    return 0;
}