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;}
};