酷站字体摄影网站免费源码

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

1493. 删除一个元素以后全为1的最长子数组 - 题解

问题描述

给定一个二进制数组 nums，你需要从中删除一个元素。请你在删掉元素后返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0。

示例

• 输入：nums = [1, 1, 0, 1]

  • 输出：3 （删除位置 2 的元素后，最长的子数组为 [1, 1, 1]）

• 输入：nums = [0, 1, 1, 1, 0, 1, 1, 0, 1]

  • 输出：5 （删除位置 4 的元素后，最长的子数组为 [1, 1, 1, 1, 1]）

解题思路

为了找到删除一个元素后最长的全 1 子数组，我们可以使用滑动窗口的技术来高效地处理此问题。具体步骤如下：

1. 定义变量：

   • n：数组的大小。
   • ans：记录最长子数组的长度。
   • left：滑动窗口的左边界。
   • cnt：数组，cnt[0] 用于计数 0 的个数，cnt[1] 用于计数 1 的个数。

2. 遍历数组：

   • 使用 right 作为滑动窗口的右边界，遍历数组。
   • 每遇到一个 nums[right]，更新计数器 cnt。

3. 调整窗口：

   • 当窗口中 0 的数量大于 1 时，移动左边界 left，直到窗口中 0 的数量不超过 1。

4. 更新结果：

   • 计算当前窗口的长度（right - left），并更新 ans。

5. 返回结果：

   • 最后返回 ans，并注意要减去 1，因为我们删除了一个元素。

代码实现

以下是使用 C++ 实现的代码：

class Solution {
public:int longestSubarray(vector<int>& nums) {int n = nums.size(), ans = 0, left = 0;int cnt[2]{}; // cnt[0] 用于记录 0 的数量，cnt[1] 用于记录 1 的数量for (int right = 0; right < n; right++) {cnt[nums[right]]++; // 更新当前数字的计数// 调整窗口的左边界while (cnt[0] > 1) { // 如果 0 的数量超过 1cnt[nums[left++]]--; // 移动左指针，减少计数}ans = max(ans, right - left); // 更新找到的最大长度}return ans; // 返回结果}
};

复杂度分析

• 时间复杂度：O(n)，每个元素最多被访问两次（一次由 right 指针，另一次由 left 指针）。
• 空间复杂度：O(1)，只使用了常量空间来存储计数器 cnt。

总结

本题的关键在于灵活使用滑动窗口来处理动态变化的子数组长度。在窗口调整过程中，需要合理管理 0 的数量，从而确保我们能在删除一个元素后找到最长的全 1 子数组。通过此解法，我们可以高效地解决问题并得到满意的结果。