1004. 最大连续1的个数 III

解题思路

重点: 题意转换。把「最多可以把 K 个 0 变成 1,求仅包含 1 的最长子数组的长度」转换为 「找出一个最长的子数组,该子数组内最多允许有 K 个 0 」。

经过上面的题意转换,我们可知本题是求最大连续子区间,可以使用滑动窗口方法。滑动窗口的限制条件是:窗口内最多有 K 个 0。

代码思路:

1.使用 l 和 r 两个指针,分别指向滑动窗口的左右边界。

2.r 主动右移: r 指针每次移动一步。当nums[r]为 0,说明滑动窗口内增加了一个 0;

3.l 被动右移: 判断此时窗口内 0 的个数,如果超过了 k,则 l 指针被迫右移,直至窗口内的 0 的个数小于等于 k 为止。

4.滑动窗口长度最大值就是所求。

示例:

以 A= [1,1,1,0,0,0,1,1,1,1,0], K = 2 为例,下面的动图演示了滑动窗口的两个指针的移动情况。

1004. 最大连续1的个数 III - 负雪明烛 的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int longestOnes(int[] nums, int k) {
int zero = 0; // 窗口中0的个数
int n = nums.length;
int res = 0;
for (int r = 0, l = 0; r < n; r++) {
if (nums[r] == 0) zero++; // r主动右移形成新的窗口
// 窗口内的0个数>k代表不符合题意->此时l应被动移动至符合对应r要求的位置
while (zero > k) {
if (nums[l] == 0) zero--;
l++;
}
// 维护每一轮r对应的窗口长度最大值就是res
res = Math.max(res, r - l + 1);
}
return res;
}

分享滑动窗口模板

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」,我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像:前脚不动,把后脚移动过来;后脚不动,把前脚向前移动。

我分享一个滑动窗口的模板,能解决大多数的滑动窗口问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] findSubArray(int[] nums){
int n = num.length; // 数组or字符串长度
int l = 0, r = 0; // 双指针,表示当前遍历的区间[l, r],闭区间
int sum = 0 // 用于统计 子数组or子区间 是否有效,根据题目可能会改成求和or计数
int res = 0 // 保存最大的满足题目要求的 子数组or子串 长度
while (r < n){ // 当右边的指针没有搜索到 数组or字符串 的结尾
sum += nums[r] // 增加当前右边指针的数字or字符的求和or计数
while 区间[l, r]不符合题意{
sum -= nums[l] // 移动左指针前需要从sum中减少l位置字符的求和or计数
l++ // 真正的移动左指针,注意不能跟上面一行代码写反
} // 此时需要一直移动左指针,直至找到一个符合题意的区间
// 到 while 结束时,我们找到了一个符合题意要求的 子数组or子串
res = Math.max(res, r - l + 1) // 需要更新结果
r++ // 移动右指针,去探索新的区间
}
return res
}

滑动窗口中用到了左右两个指针,它们移动的思路是:以右指针作为驱动,拖着左指针向前走。右指针每次只移动一步,而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移,探索未知的新区域;左指针是被迫移动,负责寻找满足题意的区间。

模板的整体思想是:

1.定义两个指针 l 和 r 分别指向区间的开头和结尾,注意是闭区间;定义 sum 用来统计该区间内的各个字符出现次数;

2.第一重 while 循环是为了判断 r 指针的位置是否超出了数组边界;当 r 每次到了新位置,需要增加 r 指针的求和/计数;

3.第二重 while 循环是让 l 指针向右移动到 [l, r] 区间符合题意的位置;当 l 每次移动到了新位置,需要减少 l 指针的求和/计数;

4.在第二重 while 循环之后,成功找到了一个符合题意的 [l, r] 区间,题目要求最大的区间长度,因此更新 res = max(res, 当前区间的长度) 。

5.r 指针每次向右移动一步,开始探索新的区间。

6.模板中的 sum 需要根据题目意思具体去修改,本题是求和题目因此把sum 定义成整数用于求和;如果是计数题目,就需要改成字典用于计数。当左右指针发生变化的时候,都需要更新 sum 。

7.另外一个需要根据题目去修改的是内层 while 循环的判断条件,即: 区间 [l, r] 不符合题意 。对于本题而言,就是该区间内的 0 的个数 超过了 2 。

滑窗题目主要有两种类型:

1.窗口大小固定,例如为10,这时候相当于左右边界必定严格同步移动。

2.左指针l不回退类型,这类型一般是新加入nums[r]使得回退必定不符合条件,旧的nums[r]已经不符合条件,这种也可以利用滑窗的思想求解。

再来一道练习题:

LC209. 长度最小的子数组

给定一个含有n个正整数的数组和一个正整数target
找出该数组中满足其和≥ target 的长度最小的连续子数组〔numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。
示例1:
输入: target = 7, nums = [2,3,1,2,4,3] 输出:2
解释:子数组[4,3]是该条件下的长度最小的了教组。
示例2:
输入: target = 4,nums = [1,4,4] 输出:1
示例3:
输入: target = 11,nums = [1,1,1,1,1,1,1,1] 输出:0

思路:

滑动窗口:

这一题最关键的字眼"≥ target 的长度最小的 连续子数组"

这个字眼可以联想到很多东西

1.连续子数组:是连续的,因此可以与前缀和进行结合(实际上sum变量是一种对于前缀和的优化写法,目的是快速计算窗口的和)

同时,连续子数组,左右指针为边界就可以确定一个连续子数组->滑动窗口

因此这一题的的提示已经非常明确了,必定是用滑窗

2.长度最小:一般来说求最小长度这种全局最优状态,可以考虑动态规划或者一路维护

这里用dp的话,状态就是nums[i]结尾的最大长度,显然不太合适,dp[i-1]与dp[i]没有很明显的联系

那么就需要一路维护,求出以nums[r]为右边界的窗口的最小长度,r∈[0,len-1]

维护好nums[0]~nums[len-1]为右边界的合法窗口长度,就是全局的合法窗口最小值,也就是所求!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 滑窗:右指针主动右移,左指针被动右移
int res = Integer.MAX_VALUE;
int len = nums.length;
int l = 0, r = 0;
// 维护当前窗口[l,r]的总和
int sum = 0;
// 主动移动右指针
for (; r < len; r++) {
// 计算当前窗口[l,r]的和:新加入的元素只有nums[r]
// r指针可能要循环多次才能找到符合条件的[l,r],因为l右移至不符合sum>=target
sum += nums[r];
// 若窗口[l,r]满足条件,统计长度并尝试将其尽可能缩小,直至不符合题意
while (sum >= target) {
// [l,r]符合条件,维护res
res = Math.min(res, r - l + 1);
// l一直右移并统计,直至不满足条件
// 这里有个很值得思考的点:为什么l指针可以义无反顾地移动至不符合条件的l+1?
// [l,r]合法;[l+1,r]不合法,而[l,r+1]及更长的不可能被统计因为只统计短的
// [l,r-1]以及更短的呢?右边界为r-1的情况已统计,因为l会直接移动到不合法且nums都为正数,因此窗口不可能继续缩小!
// 所以此时l可以义无反顾地移动至l+1
sum -= nums[l++];
}
}
// 若没有窗口符合条件就是0
return res == Integer.MAX_VALUE ? 0 : res;
}
}

为什么l指针可以义无反顾地移动至不符合条件的l+1?滑窗精髓所在->减少不必要的计算