题目描述

难度分:$1088$

输入$n$，$m(1 \leq m \leq n \leq 1.5 \times 10^6)$和长为$n$的数组$a(0 \leq a[i] \lt n)$。

定义$mex(b)$为不在数组$b$中的最小非负整数。

遍历$a$的所有长为$m$的连续子数组$b$，输出$mex(b)$的最小值。

输入样例$1$

3 2
0 0 1

输出样例$1$

1

输入样例$2$

3 2
1 1 1

输出样例$2$

0

输入样例$3$

3 2
0 1 0

输出样例$3$

2

输入样例$4$

7 3
0 0 1 2 0 1 0

输出样例$4$

2

算法

滑动窗口

假如子数组$[i,i+m)$的$Mex$值为$x$，此时如果窗口要滑到$[i+1,i+m]$，那就会删掉一个$left=A_i$，加入一个$right=A_{i+m}$。有如下两种情况：

1. 如果此时窗口内不再有$left$，需要考虑$Mex$值的更新：$(1)$ $left \lt x$，则$Mex$会减小为$left$。$(2)$ 否则$Mex$值仍然是$x$，保持不变。因为$left$不可能等于$x$，否则前一个窗口就含有$x$，与$Mex=x$矛盾。所以$left \gt x$，而把一个更大的数删掉是不会影响$Mex$值的。
2. 否则等于说又加进来了一个新数，也需要考虑$Mex$值的更新：$(1)$ 如果$right=x$，刚好补齐了$x$这个空缺，而窗口内一共就$m$个数，所以$Mex=x+1$。$(2)$ 如果$right \lt x$，因为$Mex=x$，所以小于$x$的数是本来就有的，$Mex=x$不变。$(3)$ 如果$right \gt x$，加进来一个更大的数不影响$Mex$的值，$Mex=x$仍然不变。

复杂度分析

时间复杂度

在滑动窗口的过程中每次更新窗口和$Mex$值都是$O(1)$的，因此算法整体的时间复杂度是$O(n)$。

空间复杂度

使用了一个哈希表来存储长度为$m$的子数组中的元素，因此在最差的情况下，其中可能有$m$个键值对，额外空间复杂度为$O(m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 1500010;
int a[N], m, n;

int main() {
    scanf("%d%d", &n, &m);
    unordered_map<int, int> counter;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(i <= m) {
            counter[a[i]]++;
        }
    }
    int mex = 0;
    while(counter.find(mex) != counter.end()) mex++;
    int ans = mex;
    for(int r = m + 1; r <= n; r++) {
        int left = a[r - m], right = a[r];
        --counter[left], ++counter[right];
        if(counter[left] == 0) {
            counter.erase(left);
            if(left < mex) mex = left;
        }else {
            if(right == mex) mex++;
        }
        ans = min(ans, mex);
    }
    printf("%d\n", ans);
    return 0;
}