跳至主要內容

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

ITCharge大约 2 分钟

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

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

题目链接

题目大意

描述:给定一个二进制数组 numsnums,需要从数组中删掉一个元素。

要求:返回最长的且只包含 11 的非空子数组的长度。如果不存在这样的子数组,请返回 00

说明

  • 1nums.length1051 \le nums.length \le 10^5
  • nums[i]nums[i] 要么是 00 要么是 11

示例

  • 示例 1:
输入:nums = [1,1,0,1]
输出:3
解释:删掉位置 2 的数后,[1,1,1] 包含 31
  • 示例 2:
输入:nums = [0,1,1,1,0,1,1,0,1]
输出:5
解释:删掉位置 4 的数字后,[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1]

解题思路

思路 1:滑动窗口

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

设定两个指针:leftleftrightright,分别指向滑动窗口的左右边界,保证窗口 00 的个数小于 11 个。使用 windowcountwindow\underline{}count 记录窗口中 00 的个数,使用 ansans 记录删除一个元素后,最长的只包含 11 的非空子数组长度。

  • 一开始,leftleftrightright 都指向 00

  • 如果最右侧元素等于 00,则 window_count += 1

  • 如果 windowcount>1window\underline{}count > 1 ,则不断右移 leftleft,缩小滑动窗口长度。并更新当前窗口中 00 的个数,直到 windowcount1window\underline{}count \le 1

  • 更新答案值,然后向右移动 rightright,直到 rightlen(nums)right \ge len(nums) 结束。

  • 输出答案 ansans

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 numsnums 的长度。
  • 空间复杂度O(1)O(1)