LeetCode75——Day17

一、题目

1493. Longest Subarray of 1’s After Deleting One Element

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1’s.
Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1’s is [1,1,1,1,1].
Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

1 <= nums.length <= 105
nums[i] is either 0 or 1.

二、题解

遍历每个元素，求该元素删除后，左侧及右侧连续1的数目，并统计最大值。

注意初始化l和r的语句，若为1则不断+1，若为0则直接清0

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0;
        //元素左侧1的个数
        vector<int> l(n,0);
        //元素右侧1的个数
        vector<int> r(n,0);
        l[0] = nums[0];
        r[n-1] = nums[n-1];
        for(int i = 1;i < n;i++){
            l[i] = (l[i-1] + 1) * nums[i];
        }
        for(int i = n - 2;i >= 0;i--){
            r[i] = (r[i+1] + 1) * nums[i];
        }
        int res = 0;
        for(int i = 0;i < n;i++){
            if(i == 0) res = max(res,r[i+1]);
            else if(i > 0 && i < n - 1) res = max(res,l[i-1] + r[i+1]);
            else res = max(res,l[i-1]);
        }
        return res;
    }
};
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