LeetCode 75系列 - 1493. 删掉一个元素以后全为 1 的最长子数组

题目描述

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

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

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

提示 1：

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

示例 2：

1
2
3
输入：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：

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

提示：

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

题解

核心问题为「以第 i−1 位结尾的最长连续全 1 子数组」和「以第 i+1 位开头的最长连续全 1 子数组」的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n), suf(n);
        pre[0] = nums[0];
        suf[n - 1] = nums[n - 1];

        // 顺序
        for (int i = 1; i < n; ++i) {
            // index 为 i 时，当前顺序全1长度
            pre[i] = nums[i] ? pre[i - 1] + 1 : 0;
        }

        // 逆序
        for (int i = n - 2; i >= 0; --i) {
            // index 为 i 时，当前逆序全1长度
            suf[i] = nums[i] ? suf[i + 1] + 1 : 0;
        }

        int sum{};
        for (int i = 0; i < n; ++i) {
            // 删除位置 i 后，左侧连续 1 的长度
            int preSum = i == 0 ? 0 : pre[i - 1];
            // 删除位置 i 后，右侧连续 1 的长度
            int sufSum = i == n - 1 ? 0 : suf[i + 1];
            // 将 preSum 和 sufSum 相加，表示删除位置 i 后，左右两侧连续 1 的总长度。
            sum = std::max(sum, preSum + sufSum);
        }
        return sum;
    }
};