LeetCode 1493题最优滑动窗口解法解析求助

题目描述 #

给定二进制数组nums，需删除一个元素，返回删除后仅含1的最长非空子数组的长度，若无则返回0。

• 示例1：输入nums=[1,1,0,1]，输出3
• 示例2：输入nums=[0,1,1,1,0,1,1,0,1]，输出5

待解析代码 #

class Solution(object):
    def longestSubarray(self, nums):
        ans = 0
        zero = 0
        left = 0
        for i, v in enumerate(nums):
            if v == 0:
                zero += 1
            if zero > 1:
                if nums[left] == 0:
                    zero -= 1
                left += 1
        return i - left

逻辑拆解与疑问解答 #

核心思路：滑动窗口维护「最多含1个0」的区间 #

这段代码用的是**滑动窗口（双指针）**思路，核心是维护一个窗口[left, i]，保证窗口内最多包含1个0——因为题目要求删除一个元素后全是1，相当于允许窗口里有1个0（删除它），或者全是1（删除其中一个1）。

1. 算法如何统计未被包含的1？

你对left的理解有误：它不是统计左侧的0或未计数的1，而是滑动窗口的左边界，窗口范围是[left, i]。代码没有单独统计1的数量，而是通过窗口长度间接计算有效长度：

• 窗口总长度是i - left + 1
• 因为必须删除一个元素（题目强制要求），所以有效长度是(i - left + 1) - 1 = i - left，这就是代码最后返回值的由来。

那些被left划过的元素（窗口左侧的元素），无论是1还是0，都被排除在当前窗口之外——它们所在的区间不符合「最多含1个0」的条件，因此不会被计入有效长度。窗口内的元素要么是全1（删除一个1后长度为窗口长度-1），要么含1个0（删除这个0后长度也是窗口长度-1），正好对应题目要求的结果。

2. 最长子数组在中间时，后续遍历为何不影响结果？

首先要说明：这段代码存在小瑕疵——它没有记录遍历过程中的最大有效长度，而是直接返回最后一个窗口的有效长度。但在大部分测试用例中它能得到正确结果，原因是：
滑动窗口的左边界left只会向右移动，不会回退。当最长子数组出现在中间时，后续遍历遇到新元素：

• 如果新元素是1，窗口会扩大，有效长度可能超过之前的最大值；
• 如果新元素是0，left会向右移动缩小窗口，此时有效长度可能变小，但最后返回的i-left其实等于整个数组中能找到的最大有效长度——因为当窗口缩小到符合条件时，它对应的是当前右边界i能找到的最长有效子数组，而整个遍历过程中，最大的有效长度会被保留到最后（比如示例2中，最后窗口的有效长度正好是最大值5）。

不过严格来说，这段代码是不严谨的，比如数组[1,1,0,1,1,1,0,1]，正确答案是5，但这段代码会返回4。正确的写法应该用while循环替代if来移动left，同时在每次循环中更新最大值ans：

class Solution(object):
    def longestSubarray(self, nums):
        ans = 0
        zero = 0
        left = 0
        for i, v in enumerate(nums):
            if v == 0:
                zero += 1
            # 用while循环确保窗口内0的数量<=1
            while zero > 1:
                if nums[left] == 0:
                    zero -= 1
                left += 1
            # 记录每次循环的最大有效长度
            ans = max(ans, i - left)
        return ans

内容的提问来源于stack exchange，提问作者Tianze Hua