[滑动窗口]1493. 删掉一个元素以后全为 1 的最长子数组

1493. 删掉一个元素以后全为 1 的最长子数组

1493. 删掉一个元素以后全为 1 的最长子数组 - 力扣（LeetCode）

给定一个二进制数组nums，你需要从中删除一个元素（必须删除一个，且只能删除一个），返回最长的且只包含1的非空子数组的长度。如果不存在这样的子数组，返回0。

注意：删除一个元素后，剩下的元素需要是连续的（因为是子数组）。实际上，问题可以转化为：在数组中找一个子数组，这个子数组最多只能包含一个0，然后这个子数组的长度减1（因为我们要删除一个元素）就是候选答案。但是注意，如果整个数组都是1，那么删除一个元素后，长度是原长度减1。

注意：如果整个数组都是1，那么删除一个1后，剩下的连续1的长度是n-1，而按照上述方法，我们找到的子数组（整个数组）长度为n，减去1后是n-1，符合要求。

所以算法：使用滑动窗口，维护一个窗口，窗口内最多只能有一个0。当窗口内0的个数超过1时，移动左指针。然后记录窗口大小减1的最大值。

方法思路

1. 1.​问题分析​：题目要求从二进制数组中删除一个元素后，找到最长的连续1子数组。关键在于理解删除一个元素相当于允许窗口中最多有一个0，因为删除0可以连接两段1，而删除1则减少连续1的长度。
2. 2.直觉​：使用滑动窗口维护一个最多包含一个0的子数组。窗口的扩展由右指针控制，当窗口内0的个数超过1时，左指针移动以调整窗口。
3. 3.​算法选择​：滑动窗口算法高效地遍历数组，动态调整窗口大小，确保窗口内最多只有一个0。时间复杂度为O(n)，空间复杂度为O(1)。
4. 4.​复杂度分析​：每个元素最多被访问两次（左指针和右指针各一次），因此时间复杂度为线性。仅使用几个变量，空间复杂度为常数。

解决代码

class Solution:def longestSubarray(self, nums: List[int]) -> int:ans = 0cnt0 = 0left = 0n = len(nums)for right in range(n):cnt0 += 1 - nums[right]while cnt0 > 1:cnt0 -= 1 - nums[left]left += 1ans = max(ans, right - left)return ans

代码解释

1. 1.​初始化​：ans存储最大长度，cnt0计数窗口中的0的个数，left表示窗口左边界。
2. 2.​滑动窗口​：右指针right遍历数组，更新cnt0。当cnt0超过1时，移动左指针left并调整cnt0。
3. 3.​更新结果​：每次迭代计算当前窗口长度（right - left）并更新ans。
4. 4.​返回结果​：遍历结束后返回ans，即最长连续1子数组的长度（删除一个元素后）。

该方法确保在线性时间内高效解决问题，适用于大规模数据输入。