1493. 删掉一个元素以后全为 1 的最长子数组

🟠   🔖  数组 动态规划 滑动窗口  🔗 力扣 LeetCode

题目

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 <= 10^5
• nums[i] is either 0 or 1.

题目大意

给你一个二进制数组 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 <= 10^5
• nums[i] 要么是 0 要么是 1 。

解题思路

要解决这个问题，可以通过滑动窗口的方式找到删除一个元素后所能得到的最长的只包含 1 的子数组。

1. 滑动窗口：保持一个窗口，它最多只能包含一个 0。当窗口包含超过一个 0 时，逐步移动窗口的左边界，直到窗口只包含一个 0。
2. 变量定义：定义 left 为窗口的左边界，zeroCount 记录窗口中 0 的数量，max 记录当前最大的窗口长度（只包含 1 的子数组）。
3. 遍历数组：用 right 作为窗口的右边界，每遇到一个 0，增加 zeroCount，如果 zeroCount 超过 1，移动 left 直到 zeroCount 不超过 1，在窗口大小符合条件时更新 max。
4. 考虑全是 1 的情况：如果数组全是 1，由于必须删除一个元素，最长子数组长度是 nums.length - 1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 数组的长度，每个元素最多被访问两次。
• 空间复杂度：O(1)，只使用了常数个变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
	const n = nums.length;
	let left = 0,
		zeroCount = 0,
		max = 0;
	for (let right = 0; right < n; right++) {
		if (nums[right] == 0) {
			zeroCount++;
		}
		// 如果窗口中 0 的数量超过 1，缩小窗口
		while (zeroCount > 1) {
			if (nums[left] == 0) {
				zeroCount--;
			}
			left++;
		}
		// 计算窗口长度，但排除删除的一个元素，确保当数组全是 1 时，返回 nums.length - 1
		max = Math.max(max, right - left);
	}
	return max;
};

相关题目

题号	标题	题解	标签	难度	力扣
1004	最大连续1的个数 III	[✓]	数组 二分查找 前缀和 1+	🟠	🀄️ 🔗