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

标签：数组、动态规划、滑动窗口
难度：中等

题目大意 #

给定一个二进制数组 nums，需要

要求：从数组中删掉一个元素，并返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0。

解题思路 #

维护一个元素值为 0 的元素数量少于 1 个的滑动窗口。则答案为滑动窗口长度减去窗口内 0 的个数求最大值。具体做法如下：

设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口 0 的个数小于 1 个。使用 window_count 记录窗口中 0 的个数，使用 ans 记录删除一个元素后，最长的只包含 1 的非空子数组长度。

一开始，left、right 都指向 0。
如果最右侧元素等于 0，则 window_count += 1 。
如果 window_count > 1 ，则不断右移 left，缩小滑动窗口长度。并更新当前窗口中 0 的个数，直到 window_count <= 1。
更新答案值，然后向右移动 right，直到 right >= len(nums) 结束。
输出答案 ans。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left, right = 0, 0
        window_count = 0
        ans = 0

        while right < len(nums):
            if nums[right] == 0:
                window_count += 1

            while window_count > 1:
                if nums[left] == 0:
                    window_count -= 1
                left += 1
            ans = max(ans, right - left + 1 - window_count)
            right += 1

        if ans == len(nums):
            return len(nums) - 1
        else:
            return ans