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

题目描述#

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

示例 1：

1
输入：nums = [1,1,0,1]
2
输出：3

示例 2：

1
输入：nums = [0,1,1,1,0,1,1,0,1]
2
输出：5

示例 3：

1
输入：nums = [1,1,1]
2
输出：2

解法思路#

核心思想#

删除一个元素后剩下的全 1 子数组，等价于：原数组里某个连续子数组去掉恰好一个元素后全为 1。这样的子数组内部至多含一个 0。

所以问题转化为不定长滑动窗口：求窗口内 0 的个数 $\le 1$ 的最大窗口，答案取窗口长度减一（因为其中一个元素要被删除）。

当窗口内出现两个 0 时，右移左指针收缩，直到窗口内只剩一个 0。因为滑动窗口”越长越不合法”，这正是求最大的场景。

算法步骤#

初始化 ans = left = cnt0 = 0。
枚举 right：若 nums[right] == 0，cnt0 += 1。
while cnt0 > 1：若 nums[left] == 0 则 cnt0 -= 1，left += 1。
更新 ans = max(ans, right - left)（窗口长 right-left+1 再减掉要删的 1 个元素）。
返回 ans。

逐步举例#

以 nums = [1,1,0,1] 为例（期望答案 3）：

right	元素	入窗后 cnt0	收缩	窗口	长度(减1)	ans
0	1	0	—	[0,0]	0	0
1	1	0	—	[0,1]	1	1
2	0	1	—	[0,2]	2	2
3	1	1	—	[0,3]=“101”	3	3

窗口 [0,3]=“101” 去掉中间的 0 得 “11”，长度为 2 的两侧？实际窗口 [0,3] 长度 4-1=3，对应原串把中间 0 删掉，得 “111” 长度为 3。✅

题解#

1
class Solution:
2
    def longestSubarray(self, nums: list[int]) -> int:
3
        ans = left = cnt0 = 0
4
        for right, x in enumerate(nums):
5
            if x == 0:
6
                cnt0 += 1
7
            while cnt0 > 1:
8
                if nums[left] == 0:
9
                    cnt0 -= 1
10
                left += 1
11
            ans = max(ans, right - left)
12
        return ans

1
import sys
2
sys.path.insert(0, "/workspace/projects/source/coding/sliding-window-two-pointers/02-variable-sliding-window/1493-longest-subarray-after-delete")
3
from solution import Solution
4
import unittest
5

6
class TestLongestSubarray(unittest.TestCase):
7
    def setUp(self):
8
        self.solution = Solution()
9

10
    def test_example1(self):
11
        self.assertEqual(self.solution.longestSubarray([1,1,0,1]), 3)
12

13
    def test_example2(self):
14
        self.assertEqual(self.solution.longestSubarray([0,1,1,1,0,1,1,0,1]), 5)
15

16
    def test_example3(self):
17
        self.assertEqual(self.solution.longestSubarray([1,1,1]), 2)
18

19
    def test_all_zeros(self):
20
        self.assertEqual(self.solution.longestSubarray([0,0,0]), 0)
21

22
    def test_single_one(self):
23
        self.assertEqual(self.solution.longestSubarray([1]), 0)
24

25
    def test_single_zero(self):
26
        self.assertEqual(self.solution.longestSubarray([0]), 0)
27

28
if __name__ == "__main__":
29
    unittest.main()

复杂度分析#

时间复杂度：O(n)，左右指针各遍历一次
空间复杂度：O(1)