What is the main idea behind Longest Subarray of 1's After Deleting One Element?

Treat the deletion as permission to keep a contiguous region with at most one zero. If a window has one zero, deleting it leaves only 1s; if it has no zero, you still remove one element, so the contribution is window length minus one.

Why does the sliding window work for LeetCode 1493?

This problem only cares whether a segment can become all 1s after one deletion. That is exactly the same as asking whether the segment contains at most one zero, so a two-pointer window can expand greedily and shrink only when zeros exceed one.

How does the state transition dynamic programming pattern apply here?

Use one state for consecutive 1s with no deletion used yet and another for consecutive 1s after one deletion. On a 1, both states extend; on a 0, the deleted-state takes the old no-deletion streak and the no-deletion streak resets to zero.

What should I return for an array of all 1s?

Return n - 1 because one element must be deleted even though there is no zero to remove. This is the most important edge case and the easiest way to lose correctness on this problem.

Is DP better than sliding window for this problem?

They are effectively two views of the same linear-time solution. Sliding window is often easier to explain in interviews, while the DP form makes the state transition around a zero especially explicit.

#1493

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个二进制数组 nums ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0 。提示 1：输入： nums = [1,1,0,1] 输出： 3 解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1…

数组动态规划滑动窗口

题目描述

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

提示 1：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 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] 。

示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

提示：

1 <= nums.length <= 10⁵
nums[i] 要么是 0 要么是 1 。

lightbulb

解题思路

方法一：枚举

我们可以枚举每个删除的位置 $i$ ，然后计算左侧和右侧的连续 1 的个数，最后取最大值。

具体地，我们使用两个长度为 $n+1$ 的数组 $left$ 和 $right$ ，其中 $left[i]$ 表示以 $nums[i-1]$ 结尾的连续 $1$ 的个数，而 $right[i]$ 表示以 $nums[i]$ 开头的连续 $1$ 的个数。

最终答案即为 $\max_{0 \leq i < n} \{left[i] + right[i+1]\}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [0] * (n + 1)
        right = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            if x:
                left[i] = left[i - 1] + 1
        for i in range(n - 1, -1, -1):
            if nums[i]:
                right[i] = right[i + 1] + 1
        return max(left[i] + right[i + 1] for i in range(n))

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
They mention keeping a window with at most one zero, which points directly to the one-deletion sliding window.
question_mark
They ask what happens on an all-ones array, testing whether you remember the deletion is mandatory.
question_mark
They ask for an O(N) solution without extra arrays, which favors constant-space state transitions.

warning

常见陷阱

外企场景

error
Returning the longest run of 1s without subtracting one when the current window contains no zero.
error
Treating the task as optional deletion and incorrectly answering 3 for nums = [1,1,1].
error
Resetting too aggressively on zeros and missing that one deleted zero can merge the left and right 1-runs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow deleting up to k elements, which generalizes the window from at most one zero to at most k zeros.
arrow_right_alt
Return the actual subarray boundaries after deletion instead of only the maximum length.
arrow_right_alt
Solve the streaming version where bits arrive one by one and you maintain the current best under one deletion.

help

常见问题

外企场景

继续练习

#1477 找两个和为目标值且不重叠的子数组 #1425 带限制的子序列和 #1031 两个无重叠子数组的最大和