【数据结构和算法】删掉一个元素以后全为 1 的最长子数组

简介: 这是力扣的 1493 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。又又又是一道滑动窗口的典型例题,可以帮助我们巩固滑动窗口算法。这道题很活灵活现,需要加深对题意的变相理解。给你一个二进制数组nums,你需要从中删掉一个元素。请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组,请返回 0 。

 其他系列文章导航

Java基础合集

数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一:滑动窗口

2.2 滑动窗口解题模板

三、代码

3.1 方法一:滑动窗口

四、复杂度分析

4.1 方法一:滑动窗口


前言

这是力扣的 1493 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。

又又又是一道滑动窗口的典型例题,可以帮助我们巩固滑动窗口算法。

这道题很活灵活现,需要加深对题意的变相理解。


一、题目描述

给你一个二进制数组 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

    二、题解

    2.1 方法一:滑动窗口

    思路与算法:

    重点:题意转换。把「 返回最长的且只包含 1 的非空子数组的长度 」转换为 「 返回最长带有一个 0 的非空子数组的长度 - 1 」。

    经过上面的题意转换,我们可知本题是求最大连续子区间,可以使用滑动窗口方法。滑动窗口的限制条件是:窗口内最多有 1 个 0。

    可以使用我多次分享的滑动窗口模板解决,模板在代码之后。

    再次申明模板很重要,可以解决一些列的题目。

    首先定义四个变量:

      1. 左指针
      2. 右指针
      3. 最长的子串长度
      4. 0 的数量

      image.gif编辑

      代码思路:

        1. 使用 left 和 right 两个指针,分别指向滑动窗口的左右边界。
        2. right 主动右移:right 指针每次移动一步。当 nums[right] 为 0,说明滑动窗口内增加了一个 0;
        3. left 被动右移:判断此时窗口内 0 的个数,如果超过了 K,则 left 指针被迫右移,直至窗口内的 0 的个数小于等于 K 为止。
        4. 滑动窗口长度的最大值就是所求。记得最后要减去 1 ,因为子数组里还多了一个 0 。

        image.gif编辑

        2.2 滑动窗口解题模板

        滑动窗口算法是一种常用的算法,用于解决数组或列表中的子数组问题。下面是一个滑动窗口算法的解题模板:

          1. 定义窗口大小:首先需要确定滑动窗口的大小,即每次滑动时包含的元素个数。
          2. 初始化窗口:将窗口的起始位置设置为0,窗口大小设置为n,其中n为数组或列表的长度。
          3. 计算窗口中的元素和:使用一个变量sum来记录当前窗口中的元素和,初始值为0。
          4. 移动窗口:从左到右依次遍历数组或列表,每次将当前元素加入窗口中,并更新sum的值。
          5. 判断是否满足条件:在移动窗口的过程中,不断判断当前窗口中的元素和是否满足题目要求。如果满足条件,则返回当前窗口中的元素和。
          6. 移动窗口:如果当前窗口中的元素和不满足题目要求,则将窗口向右移动一位,并更新sum的值。
          7. 重复步骤4-6,直到遍历完整个数组或列表。

          下面是一个具体的例子,使用滑动窗口算法求解数组中连续子数组的最大和:

          def maxSubArray(nums):  
              if not nums:  
                  return 0  
              max_sum = current_sum = nums[0]  
              for i in range(1, len(nums)):  
                  current_sum = max(nums[i], current_sum + nums[i])  
                  max_sum = max(max_sum, current_sum)  
              return max_sum

          image.gif

          在这个例子中,我们使用一个变量max_sum来记录当前最大子数组的和,一个变量current_sum来记录当前窗口中的元素和。在遍历数组的过程中,不断更新current_sum的值,并判断是否满足题目要求。如果满足条件,则更新max_sum的值。最后返回max_sum即可。


          三、代码

          3.1 方法一:滑动窗口

          Java版本:

          class Solution {
              public int longestSubarray(int[] nums) {
              int left = 0, right = 0, zero = 0, longestSubarray = 0, n = nums.length;
                  while (right < n) {
                      if (nums[right] == 0) zero++;
                      if (zero > 1) {
                          left++;
                          if (nums[left - 1] == 0) zero--;
                      }
                      if (zero == 1 || right == n - 1) {
                          longestSubarray = Math.max(longestSubarray, right - left + 1);
                      }
                      right++;
                  }
                  return longestSubarray - 1;
              }
          }

          image.gif

          C++版本:

          class Solution {
          public:
              int longestSubarray(vector<int>& nums) {
                  int left = 0, right = 0, zero = 0, longestSubarray = 0, n = nums.size();
                  while (right < n) {
                      if (nums[right] == 0) zero++;
                      if (zero > 1) {
                          left++;
                          if (nums[left - 1] == 0) zero--;
                      }
                      if (zero == 1 || right == n - 1) {
                          longestSubarray = max(longestSubarray, right - left + 1);
                      }
                      right++;
                  }
                  return longestSubarray - 1;
              }
          };

          image.gif

          Python版本:

          class Solution:
              def longestSubarray(self, nums: List[int]) -> int:
                  left = 0
                  right = 0
                  zero = 0
                  longestSubarray = 0
                  n = len(nums)
                  while right < n:
                      if nums[right] == 0:
                          zero += 1
                      if zero > 1:
                          left += 1
                          if nums[left - 1] == 0:
                              zero -= 1
                      if zero == 1 or right == n - 1:
                          longestSubarray = max(longestSubarray, right - left + 1)
                      right += 1
                  return longestSubarray - 1

          image.gif

          Go版本:

          func longestSubarray(nums []int) int {
              left := 0
              right := 0
              zero := 0
              longestSubarray := 0
              n := len(nums)
              for right < n {
                  if nums[right] == 0 {
                      zero++
                  }
                  if zero > 1 {
                      left++
                      if nums[left-1] == 0 {
                          zero--
                      }
                  }
                  if zero == 1 || right == n-1 {
                      longestSubarray = max(longestSubarray, right-left+1)
                  }
                  right++
              }
              return longestSubarray - 1
          }
          func max(a, b int) int {
              if a > b {
                  return a
              }
              return b
          }

          image.gif


          四、复杂度分析

          4.1 方法一:滑动窗口

            • 时间复杂度:O(N),因为每个元素只遍历了一次。
            • 空间复杂度:O(1),因为使用了常数个空间。


            目录
            打赏
            0
            1
            1
            0
            29
            分享
            相关文章
            企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
            企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
            19 1
            |
            10天前
            |
            基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
            跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
            30 0
            |
            4月前
            |
            算法系列之数据结构-Huffman树
            Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
            129 3
             算法系列之数据结构-Huffman树
            |
            4月前
            |
            算法系列之数据结构-二叉搜索树
            二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
            117 22
            关于员工上网监控系统中 PHP 关联数组算法的学术解析
            在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
            63 7
            |
            4月前
            |
            算法系列之数据结构-二叉树
            树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
            107 10
             算法系列之数据结构-二叉树
            C 408—《数据结构》算法题基础篇—链表(下)
            408考研——《数据结构》算法题基础篇之链表(下)。
            149 30
            232.用栈实现队列,225. 用队列实现栈
            在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
            栈区的非法访问导致的死循环(x64)
            这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
            27 0
            栈区的非法访问导致的死循环(x64)
            |
            8月前
            |
            非递归实现后序遍历时,如何避免栈溢出?
            后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
            192 59

            热门文章

            最新文章

            AI助理

            你好,我是AI助理

            可以解答问题、推荐解决方案等