Gemini Flash-Lite 题解

这道题目看似复杂，实则是考察数学规律+滑动窗口的变体。

题目分析

我们需要找到最长的连续子数组，使得对于其中的相邻元素，满足。这意味着这个子数组应该是类似 x, x+1, x+2, ... 这样的形式。

如果我们把这个条件变形：

也就是说，如果一个连续子数组满足条件，那么对于该子数组内的任意位置， 的值必须是完全相同的！

解题思路

转化数据：我们构建一个新数组，其中。题目就变成了：在数组中，找出一个最长的连续子数组，使得该子数组内最多有个元素不等于某一个目标值。
滑动窗口：对于每一个可能出现的（即的值），我们使用滑动窗口来统计有多少个元素与它相等。

实际上，我们只需要统计数组中相同元素的连续段以及利用次修改将它们拼凑起来。
由于可能很大，我们可以使用 std::map 来存储出现的下标列表。

C++ 代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;

    // 用 map 存储 B[i] = A[i] - i 出现的所有下标
    map<int, vector<int>> mp;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        mp[a - i].push_back(i);
    }

    int max_len = 0;
    // 遍历每一种可能的目标值 (A[i] - i)
    for (auto const& [val, indices] : mp) {
        int m = indices.size();
        // 对当前目标值，滑动窗口寻找包含最多可修改次数的区间
        // 窗口内包含 m_count 个原本就符合的数，修改 K 次
        // 最长长度 = (窗口内符合的数) + K，但不能超过数组总长 N
        for (int left = 0, right = 0; right < m; ++right) {
            while (indices[right] - indices[left] - (right - left) > K) {
                left++;
            }
            max_len = max(max_len, min(N, (right - left + 1) + K));
        }
    }

    cout << max_len << endl;

    return 0;
}

核心逻辑解释

1. 为什么是？

如果，那么。这证明了只要满足“公差为 1”的序列，它们对应的值一定是相等的。

2. 滑动窗口的判断条件：

在 indices 数组（存储了所有等于某值的下标）中，区间 [left, right] 内已经有 (right - left + 1) 个元素符合条件。

我们需要填充的空隙个数是 indices[right] - indices[left] - (right - left)。如果这个空隙数小于等于，说明我们能通过修改将它们连成一片。

3. 复杂度：

由于每个元素只会被访问常数次，总时间复杂度为（取决于 map 的操作），这在的数据规模下表现非常优秀。

这个思路将“修改”转换为了“寻找最长且缺口小于的下标序列”，是处理此类区间问题的常用高阶技巧。

题目分析

解题思路

C++ 代码实现

核心逻辑解释

暂无评论