2020/3/7
题目描述
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
若队列为空，pop_front 和 max_value 需要返回 -1
示例
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
相关标签
双指针
Sliding window
解题思路
算法：
可以通过利用两个指针 (left, right) 来遍历这个数组，其中 right 指针直接越过不为0的值，right 与 left 之间始终保持最多 K 个 0 值。复杂度分析：
时间复杂度：O(n)，一次遍历
空间复杂度：O(1)，只有几个指针的额外空间
源代码
impl Solution {
pub fn longest_ones(a: Vec<i32>, k: i32) -> i32 {
let (mut left, mut right, mut remain, mut res) = (0, 0, k, 0);
let len = a.len();
while right < len {
if a[right] == 0 {
if remain == 0 {
while a[left] == 1 {
left += 1;
}
left += 1;
}
else {
remain -= 1;
}
}
res = std::cmp::max(right-left+1, res);
right += 1;
}
res as i32
}
}
执行用时 : 4 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.2 MB, 在所有 Rust 提交中击败了100.00%的用户
总结
此题为滑动窗口的一个经典运用。max 的更新时机需要考虑。
