type
status
date
slug
summary
tags
category
icon
password
题目：
给定一个二进制数组
nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [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：
输入：nums = [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。
提示：
1 <= nums.length <= 105
nums[i]不是0就是1
0 <= k <= nums.length
方法1：
二分搜索 + 前缀和
- 时间复杂度：
- 空间复杂度：
使用前缀和得到记录0的个数的前缀和数组，遍历所有右节点，使用二分找到左节点使得区间内的0的个数小于等于k，得到最长前缀长度。
lower_bound函数：
方法2：
滑动窗口 + 前缀和
- 时间复杂度：
- 空间复杂度：
前缀和数组是单调的，因此随着增大，的值单调递增。于是使用动态窗口维护和，即在移动的时候只需要同步向右移动到最小满足的位置即可。
由于使用了滑动窗口，不需要显式地计算并保存前缀和数组。使用两个变量动态保存当前位置的前缀和
总结：
前缀和的使用：看到这种与前面数量或者数值的和有关的应当使用前缀和。
滑动窗口与前缀和连用：可以省去前缀和数组建立。
- Author:灵檠
- URL:https://blog.ly-qing.lol/article/0d31a228-6bae-4d3e-9b6b-a467e25bbc53
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!