526互联

[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element

发布时间 2023-06-29 05:06:26作者: CNoodle

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 的最长子数组。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是滑动窗口。题目告诉我们可以最多删除一个元素，并且找的是只包含 1 的子数组。那么我们可以换一个思考方式，我们去找最多只包含一个 0 的最长的子数组，这样就可以直接套用76题的模板了。当我们发觉目前这一段子数组里出现超过一个 0 的时候，就可以考虑开始移动 start 指针了。

这道题跟1004题类似，你一看就知道是滑动窗口，但是如果你直接按照题目要求你找的条件去套，发觉是无法直接套用滑动窗口的代码的，需要转换一下思路才行。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int longestSubarray(int[] nums) {
 3         int start = 0;
 4         int end = 0;
 5         int count = 0;
 6         int res = 0;
 7         while (end < nums.length) {
 8             if (nums[end] == 0) {
 9                 count++;
10             }
11             end++;
12             while (count > 1) {
13                 if (nums[start] == 0) {
14                     count--;
15                 }
16                 start++;
17             }
18             res = Math.max(res, end - start - 1);
19         }
20         return res;
21     }
22 }

 

LeetCode 题目总结