一、 问题分析

问题的核心是寻找一个长度 的连续子区间 ，使得 最大化。

  • MAX：区间内的最大元素。
  • MEX：区间内未出现的最小非负整数（从 0 开始）。
  • 约束：，这意味着算法必须达到 或 的时间复杂度。由于涉及连续区间，通常考虑滑窗、单调栈或性质挖掘。

二、 性质：单调性与局部最优

为了最大化 ，我们需要定性分析这两个指标随区间范围变化的趋势：

  1. 单调性分析：

    • MAX的单调性：当区间范围 扩大时， 的值单调不减（集合越大，最大值可能变大）。
    • MEX的单调性：当区间范围 扩大时， 的值单调不减（包含的数越多，原本缺失的最小非负整数可能会被填补，导致 MEX 增大）。

  2. 核心猜想：相邻二元组即优原则 在处理 时，虽然扩大区间可能增加 ，但同时极易增加 。 定理：对于任意长度 的区间 ，总能找到一个长度为 2 的子区间 ，使得 。

    证明思路： 设区间 的最大值为 。由于区间长度 ，索引 至少有一个相邻元素（ 或 ）也在序列 中。 考虑相邻二元组 ：

    • 。
    • 由于 是 的子集，根据 MEX 的定义，集合越小 MEX 越小，即 。
    • 因此，。

    这意味着，最大值一定可以在某个长度为 2 的区间中取得。

三、 代码实现：线性扫描二元组

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];

        int ans = -1e9;
        for (int i = 0; i + 1 < n; i++) {
            int M = max(a[i], a[i + 1]);
            int mex;
            if (a[i] != 0 && a[i + 1] != 0) {
                mex = 0;
            } else if (a[i] != 1 && a[i + 1] != 1) {
                mex = 1;
            } else {
                mex = 2;
            }
            ans = max(ans, M - mex);
        }

        cout << ans << "\n";
    }
}

四、 复杂度分析

1. 时间复杂度：

  • 算法仅需一次线性扫描即可得出结论。对于每一组测试数据，操作次数为 次常数级计算。

2. 空间复杂度： 或

  • 若读取整个数组，空间复杂度为 。
  • 由于只需要当前元素和前一个元素，理论上可以采用流式读取，将空间优化至 （不计输入缓冲区）。