有好几种解法，首先DP可以做。因为我们每翻转一个0，之后整个长度取决于左边和右边1的数量，我们可以记录每个0左边和右边的1的长度，最后取相加最大。时间空间复杂度都是O(n)，代码如下：
那么如果我们generalize这个问题，翻转k个0之后的最大长度。我们显然无法用DP。我们考虑其他的方法，假设我们将整个数组翻转，0变成1，1变成0，在求出presum数组。presum数组每加1一次，就代表原数组位置为0，如果我们允许k个0，也就是把问题转化为，presum数组差等于k的最长的subarray（presum数组一定是递增的）。我们把所有差等k的求出来就行了，时间复杂度O(n)，空间复杂度O(n)，代码如下：
如果我们在进一步generalize，数组中可以存在任何数，翻转k个0之后的最长连续不为零子区间。我们没法用presum了。从左到右遍历，每次更新右边界，同时我们用queue保存所有0的位置，并且记录左边界，当queue的size大于k之后，我们更新左边界为queue.front() + 1即可，这个区间还是满足只有k个0的条件。然后我们记录最大值，类似two pointer的解法。时间复杂度O(n)，空间复杂度O(k)，代码如下：
No comments:
Post a Comment