这是一个非常经典的算法题，通常被称为“滑动窗口”（Sliding Window）问题。
题目分析
简单来说，题目要求我们找到一个最长的连续区域，这个区域内最多只能包含 个 0（因为我们可以把这 个 0 变成 1）。
如果我们将“把 变成 ”这个操作看作是“消耗掉一个魔法次数”，那么问题就转化为了：找出一个最长的子数组，其中包含的 的个数不超过 个。
解题思路：滑动窗口
我们可以想象有一个“窗口”在数组上从左向右滑动：
- 右指针 (
right)：负责向右移动，把数组元素一个个纳入窗口中。 - 左指针 (
left)：当窗口内包含的0的个数超过了 ，说明当前窗口不合法了，我们需要移动左指针，把窗口左边的元素移出去，直到窗口内0的个数重新降到 以内。 - 记录最大值：在每一步移动中，窗口的大小（
right - left + 1）就是当前满足条件的一个连续1的长度。我们随时记录这个长度的最大值即可。
代码实现 (C++)
#include <iostream>
#include <vector>
#include <algorithm> // 为了使用 max 函数
using namespace std;
int main() {
// 优化输入输出速度
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
if (!(cin >> n >> k)) return 0;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
int left = 0, zero_count = 0, max_len = 0;
// 滑动窗口：right 是窗口的右边界
for (int right = 0; right < n; ++right) {
// 如果进入窗口的是 0，计数器加 1
if (nums[right] == 0) {
zero_count++;
}
// 如果 0 的数量超过了 k，缩减窗口左侧
while (zero_count > k) {
if (nums[left] == 0) {
zero_count--;
}
left++;
}
// 更新当前能达到的最长长度
max_len = max(max_len, right - left + 1);
}
cout << max_len << endl;
return 0;
}
为什么这个方法高效？
- 时间复杂度：。虽然代码里有个
while循环，但right指针只从头走到尾一次，left指针也只从头走到尾一次，每个元素最多被访问两次。这比暴力双重循环（）要快得多，能够轻松处理 的数据规模。 - 空间复杂度：（用于存储数组）或 （如果边读边处理）。
总结
对于这类“求满足条件的连续子序列”的问题，滑动窗口几乎是首选方案。它的核心就是：通过移动左边界来维护窗口的合法性，同时通过右边界来寻找最优解。
暂无评论