第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1004. 最大连续 1 的个数 III

题目地址(1004. 最大连续 1 的个数 III)

题目描述

1
给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。
2
3
返回仅包含 1 的最长(连续)子数组的长度。
4
5
6
7
示例 1:
8
9
输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
10
输出:6
11
解释:
12
[1,1,1,0,0,1,1,1,1,1,1]
13
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
14
15
示例 2:
16
17
输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
18
输出:10
19
解释:
20
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
21
粗体数字从 0 翻转到 1,最长的子数组长度为 10。
22
23
24
25
提示:
26
27
1 <= A.length <= 20000
28
0 <= K <= A.length
29
A[i] 为 0 或 1
Copied!

前置知识

-

公司

  • 暂无

思路

这道题我在 字节跳动的算法面试题是什么难度? 提到过这道题的换皮题。大家可以将这两道题目结合起来理解。接下来,我们看下这道题如何解决。
如果题目没有最多可以将 K 个值从 0 变成 1 。这个条件,那么会很简单,是一个常规的滑动窗口模板题。 我们加上这个条件对问题有什么样的影响呢?
这道题我们只需要记录下加入窗口的是 0 还是 1:
  • 如果是 1,我们什么都不用做
  • 如果是 0,我们将 K 减 1
相应地,我们需要记录移除窗口的是 0 还是 1:
  • 如果是 1,我们什么都不做
  • 如果是 0,说明加进来的时候就是 0,加进来的时候我们 K 减去了 1,这个时候我们再加回去 1。
如果 K 减少到负数,则收缩窗口大小。不断用满足条件的窗口大小更新答案即可。

为什么这种思路可行?

这其实就是滑动窗口的常见套路。 这种算法可行的根本原因在于其本身就是暴力枚举的优化。如果让你用最暴力的解法如何求解呢?无非就是枚举所有的子数组,这需要 $O(N^2)$ 的时间复杂度,接下来判断子数组是否满足最多将 k 个 0 变成 1,子数组全部为 1。如果满足则更新答案即可。 如何对暴力解进行优化呢?
比如现在是判断的子数组 A[2:3],我们计算出 A[2:3] 有一个 0,也就是说需要将一个 0 变成 1 才行。那么当我们继续判断子数组 A[2:4],我们只需要判断 A[4],同时结合 A[2:3]的计数信息即可。滑动窗口就是专门优化这种每次只在端点变化,中间都不变,从而省去了中间即重复计算,进而将窗口内的计数信息从 O(w) 降低到 O(1),其中 w 为窗口大小。
接下来,我们继续优化。实际上也是没有必要两层循环枚举所有子数组的。而是在 $O(n)$ 的时间就可以枚举所有的合法子数组。为什么呢?这是双指针的常见套路。其实你可以换个角度思考:
所有的子数组就是
  • 以索引 0 为右端点的所有子数组
  • 加上以索引 1 为右端点的所有子数组
  • 加上以索引 2 为右端点的所有子数组
  • ...
  • 加上以索引 n - 1 为右端点的所有子数组,其中 n 为数组长度
这样的话我们就可以使用双指针技巧。右指针模拟右端点,使用左指针模拟左端点了。如果以索引 i 为右端点的子数组 0 的个数不大于 k,那么左指针 l 没必要右移,因为当前右指针 r 和所有的索引 i, 其中 l <= i <= r 的组合 0 的个数都不会大于 k,但是子数组还更短了,不可能是答案,因此我们直接右移右指针,这是算法的关键。通过这种方式算法的时间复杂度可从 $O(n^2)$ 降低到 $n$。

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def longestOnes(self, A: List[int], K: int) -> int:
3
i = ans = 0
4
5
for j in range(len(A)):
6
K -= A[j] == 0
7
while K < 0:
8
K += A[i] == 0
9
i += 1
10
ans = max(ans, j - i + 1)
11
return ans
Copied!
甚至更简洁:
1
class Solution:
2
def longestOnes(self, A: List[int], K: int) -> int:
3
i = 0
4
5
for j in range(len(A)):
6
K -= 1 - A[j]
7
if K < 0:
8
K += 1 - A[i]
9
i += 1
10
return j - i + 1
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。