题目描述

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

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

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

样例

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

输入：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]。

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

输入：nums = [1,1,0,0,1,1,1,0,1]
输出：4

输入：nums = [0,0,0]
输出：0

限制

• 1 <= nums.length <= 10^5
• nums[i] 要么是 0 要么是 1。

算法1

(动态规划) $O(n)$

1. 设状态 $f(i)$ 表示以 $i$ 为结尾没有删除元素时最长连续 1 的长度，$g(i)$ 表示以 $i$ 为结尾且删除过一个元素时最长连续 1 的长度。有效下标从 0 开始。
2. 初始时，如果 $nums[0]$ 为 0，则 $f(0) = g(0) = 0$；如果 $nums[0]$ 为 1，则 $f(0) = 1, g(0) = 0$。
3. 转移时，如果当前元素为 0，则可以选择删除当前元素，从 $f(i - 1)$ 转移到 $g(i)$，也可以重置 $f(i)$，所以有 $g(i) = f(i - 1)$，$f(i) = 0$。
4. 如果当前元素为 1，对于 $g$ 来说，有两种选择，一种是删除当前元素，一种是延长上一次的 $g$，所以有 $g(i) = \max(f(i - 1), g(i - 1) + 1)$。对于 $f$，显然延长上一次的 $f$，所以有 $f(i) = f(i - 1) + 1$。
5. 最终答案为 $\max(g(i))$。
6. 由于每次转移仅依赖于上一位置的状态，所以可以空间优化掉状态数组。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 优化后，仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        int f, g;

        if (nums[0] == 0) {
            f = g = 0;
        } else {
            f = 1; g = 0;
        }

        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == 0) {
                g = f;
                f = 0;
            } else {
                g = max(f, g + 1);
                f++;
            }

            ans = max(ans, g);
        }

        return ans;
    }
};

算法2

(滑动窗口，双指针) $O(n)$

1. 我们求出最多只有一个 0 的最大窗口。
2. 对于每个右端点 $r$，求出最小的 $l$，满足闭区间 [l, r] 中最多只有一个 0。更新答案 $ans = \max(ans, r - l)$。
3. 注意到，$l$ 是随着 $r$ 移动单调不减的，所以可以使用双指针在线性时间内解决。

时间复杂度

• 每个位置最多被访问两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;

        for (int l = 0, r = 0, cnt = 0; r < n; r++) {
            if (nums[r] == 0)
                cnt++;

            while (l <= r && cnt > 1) {
                if (nums[l] == 0)
                    cnt--;
                l++;
            }

            ans = max(ans, r - l);
        }

        return ans;
    }
};