Solution

题目链接:1493. 删掉一个元素以后全为 1 的最长子数组

难度:1423(难度评级:6)

题面:给你一个二进制数组 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 <= 105
nums[i] 要么是 0 要么是 1 。

题意:需要我们求一个数组中最长全为1的子数组长度,并且需要删掉一个数

分析问题: 那么对于每一位上的数,就有以下几种情况：

1. 当前位置为1,则 ans + 1
2. 当前位置为0,删除当前位置,则 ans 不变
3. 当前位置为0,且没有删除的机会,则找到一个删除的位置,重新开始计数长度

我们通过这里可以发现满足滑动窗口的两个性质：

1. 连续性 子数组需要连续选取
2. 左右边界 其实就是两边为0的一段长度

1. 滑动窗口

因为只能删除一个元素,因此保证窗口内0的数量不大于1,如果大于1,则证明当前窗口需要移动左边界,即找到窗口内第一个0的位置。虽然有两层循环，但每个位置只是遍历了两次。

• 时间复杂度为 O(n),空间复杂度为 O(1)

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int ans = 0;
        int cnt_zero = 0;
        int left = 0;

        for (int right = 0; right < nums.size(); right++) 
        {
            cnt_zero += 1 - nums[right]; 
            while (cnt_zero > 1) 
            { 
                cnt_zero -= 1 - nums[left]; 
                left++;
            }
            ans = max(ans, right - left);
        }
        return ans;
    }
};

2. 滑动窗口优化

由上述滑动窗口思路可得，每次更新窗口边界时，需要找到窗口内第一个为0的位置。我们完全可以使用一个变量 pre 来记录下一个左边界，从而实现一个循环完成操作。

• 注意：这里设pre的初始值为-1,是为了防止第一个位置为0导致计数错误

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

        int j = 0;
        int pre = -1;

        for(int i = 0; i < n; i++)
        {
            if(nums[i] == 0)
            {
                j = pre + 1;
                pre = i;
            }
            ans = max(ans, i - j);
        }

        return ans;
    }
};

3. 动态规划思路

1. 问题分析：需要找到数组中最长的连续1的子数组,允许删除其中一个元素(可以是0或1),最终返回这个最长子数组的长度。

2. 动态规划思路：

   • 使用两个状态变量dp0和dp1
   • dp0表示：以当前位置为结尾,且没有删除过元素的最长连续1的子数组长度
   • dp1表示：以当前位置为结尾,且已经删除过一个元素的最长连续1的子数组长度

3. 状态转移规则：

   • 当前元素是1时：
     • dp0可以直接延续前一个dp0并加1(因为继续保持不删除元素)
     • dp1可以选择延续前一个dp1加1(继续保持已删除状态),或者从dp0延续(在当前位置删除元素)
   • 当前元素是0时：
     • dp0必须重置为0(因为出现了0,且不允许删除)
     • dp1可以从dp0延续(在当前位置删除这个0)

4. 初始值设置：

   • dp0初始化为nums[0]，表示第一个元素如果是1则长度为1，否则为0
   • dp1初始化为0，因为一开始还没有删除任何元素

5. 结果计算：

   • 每次迭代都更新最大值ans，最终ans就是删除一个元素后最长的全1子数组长度

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

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