Longest Subarray of 1 After Deleting one Element

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

分析

定义两个指针 i 和 j，表示滑动窗口的左右边界
使用变量 cnt 记录窗口中 0 的个数
遍历数组 nums ：
- 如果当前元素是 0，则将 cnt 加 1
- 如果 cnt > 1 ，说明窗口内多于一个 0，不符合题目要求，需要将左指针 j 向右移动，并根据移出的元素更新 cnt
- 每次更新窗口长度 res = max(res, i - j + 1)
遍历完成后，结果为 res - 1，因为必须删除一个元素

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    int longestSubarray(vector<int>& nums)
    {
        int res = 0;       // 最大连续 1 的长度
        int cnt = 0;       // 当前窗口中 0 的数量
        for (int i = 0, j = 0; i < nums.size(); ++i)
        {
            if (nums[i] == 0)
                ++cnt;    // 遇到 0，增加计数
            while (cnt > 1)  // 如果窗口内 0 的数量超过 1
            {
                if (nums[j] == 0)
                    --cnt; // 左指针移出 0，减少计数
                ++j;       // 缩小窗口
            }
            res = std::max(res, i - j + 1); // 更新最大长度
        }
        return res - 1; // 因为必须删掉一个元素
    }
};