如何根据「数据范围」调整自己用什么算法 ...
题目描述
这是 LeetCode 上的 1004. 最大连续 1 的个数 III，难度为 Medium。
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
示例 2：
提示：
1 <= A.length <= 200000 <= K <= A.lengthA[i]为 0 或 1
动态规划解法（TLE）
看到本题，其实首先想到的是 DP，但是 DP 是 $O(nk)$ 算法。
看到了数据范围是 $10^4$，那么时空复杂度应该都是 $10^8$。
空间可以通过「滚动数组」优化到 $10^4$，但时间无法优化，会超时。
PS. 什么时候我们会用 DP 来解本题？通过如果 K 的数量级不超过 1000 的话，DP 应该是最常规的做法。
时间复杂度：$O(nk)$
空间复杂度：$O(k)$
前缀和 + 二分 解法
从数据范围上分析，平方级别的算法过不了，往下优化就应该是对数级别的算法。
因此，很容易我们就会想到「二分」。
当然还需要我们对问题做一下等价变形。
最大替换次数不超过 k 次，可以将问题转换为找出连续一段区间 [l,r]，使得区间中出现 0 的次数不超过 k 次。
我们可以枚举区间 左端点/右端点 ，然后找到其满足「出现 0 的次数不超过 k 次」的最远右端点/最远左端点。
为了快速判断 [l,r] 之间出现 0 的个数，我们需要用到前缀和。
假设 [l,r] 的区间长度为 len，区间和为 tot，那么出现 0 的格式为 len - tol，再与 k 进行比较。
由于数组中不会出现负权值，因此前缀和数组具有「单调性」，那么必然满足「其中一段满足 len - tol <= k，另外一段不满足 len - tol <= k」。
因此，对于某个确定的「左端点/右端点」而言，以「其最远右端点/最远左端点」为分割点的前缀和数轴，具有「二段性」。可以通过二分来找分割点。
时间复杂度：$O(n\log{n})$
空间复杂度：$O(n)$
*关于二分结束后再次 check 的说明：由于「二分」本质是找满足某个性质的分割点，通常我们的某个性质会是「非等值条件」，不一定会取得 =。*
例如我们很熟悉的：从某个非递减数组中找目标值，找到返回下标，否则返回 -1。
*当目标值不存在，「二分」找到的应该是数组内比目标值小或比目标值大的最接近的数。因此二分结束后先进行 check 再使用是一个好习惯。*
双指针解法
由于我们总是比较 len、tot 和 k 三者的关系。
因此我们可以使用「滑动窗口」的思路，动态维护一个左右区间 [j, i] 和维护窗口内和 tot。
右端点一直右移，左端点在窗口不满足「len - tol <= k」的时候进行右移。
即可做到线程扫描的复杂度：
时间复杂度：$O(n)$
空间复杂度：$O(1)$
总结
除了掌握本题解法以外，我还希望你能理解这几种解法是如何被想到的（特别是如何从「动态规划」想到「二分」）。
根据数据范围（复杂度）调整自己所使用的算法的分析能力，比解决该题本身更加重要。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
版权声明: 本文为 InfoQ 作者【宫水三叶的刷题日记】的原创文章。
原文链接:【http://xie.infoq.cn/article/d886bb45290bbd50461d2b314】。文章转载请联系作者。
算法爱好者，退役 OIer 2020.03.07 加入
公众号「宫水三叶的刷题日记 」。每天十分钟，快乐学算法 ~
评论