给你一个二进制数组 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
。
方法一:枚举
枚举删除的位置
因此,我们可以先遍历一遍数组,统计每个位置 left
数组;然后再从右向左遍历一遍数组,统计每个位置 right
数组,最后枚举删除的位置
时间复杂度 nums
的长度。
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
left = [0] * n
right = [0] * n
for i in range(1, n):
if nums[i - 1] == 1:
left[i] = left[i - 1] + 1
for i in range(n - 2, -1, -1):
if nums[i + 1] == 1:
right[i] = right[i + 1] + 1
return max(a + b for a, b in zip(left, right))
class Solution {
public int longestSubarray(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
for (int i = 1; i < n; ++i) {
if (nums[i - 1] == 1) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; --i) {
if (nums[i + 1] == 1) {
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, left[i] + right[i]);
}
return ans;
}
}
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
vector<int> right(n);
for (int i = 1; i < n; ++i) {
if (nums[i - 1] == 1) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 2; ~i; --i) {
if (nums[i + 1] == 1) {
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, left[i] + right[i]);
}
return ans;
}
};
func longestSubarray(nums []int) int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := 1; i < n; i++ {
if nums[i-1] == 1 {
left[i] = left[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if nums[i+1] == 1 {
right[i] = right[i+1] + 1
}
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, left[i]+right[i])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}