Medium

题目描述

给你一个二进制数组 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^5
  • nums[i] 不是 0 就是 1

解题思路

解题思路

这道题要求删除一个元素后，找到最长的只包含 1 的子数组。核心思路是使用滑动窗口技术。

关键观察： 删除一个元素后得到最长的全 1 子数组，等价于在原数组中找到一个最长的子数组，该子数组最多包含一个 0。

滑动窗口解法（推荐）

使用双指针维护一个滑动窗口，保证窗口内最多有一个 0：

  1. 用 left 和 right 指针维护窗口边界
  2. 用 zeros 计数窗口内 0 的个数
  3. 当窗口内 0 的个数超过 1 时，移动左指针缩小窗口
  4. 每次更新答案为窗口大小减 1（因为必须删除一个元素）

时间复杂度： O(n) - 每个元素最多被访问两次
空间复杂度： O(1) - 只使用常数额外空间

动态规划解法

也可以用动态规划思想，维护当前位置左边连续 1 的个数和右边连续 1 的个数，但滑动窗口解法更直观高效。

代码实现

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int left = 0, zeros = 0, maxLen = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] == 0) {
                zeros++;
            }
            
            while (zeros > 1) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left = zeros = max_len = 0
        
        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1
            
            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            
            max_len = max(max_len, right - left)
        
        return max_len

public class Solution {
    public int LongestSubarray(int[] nums) {
        int left = 0, zeros = 0, maxLen = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] == 0) {
                zeros++;
            }
            
            while (zeros > 1) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left);
        }
        
        return maxLen;
    }
}

var longestSubarray = function(nums) {
    let left = 0, zeros = 0, maxLen = 0;
    
    for (let right = 0; right < nums.length; right++) {
        if (nums[right]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度滑动窗口解法
时间复杂度O(n)
空间复杂度O(1)

相关题目