当前位置: 首页 > article >正文

python-leetcode-删掉一个元素以后全为 1 的最长子数组

1493. 删掉一个元素以后全为 1 的最长子数组 - 力扣(LeetCode)

可以使用滑动窗口的方式来解决这个问题。我们要找到最长的全 1 子数组,但必须删除一个元素,因此可以将问题转化为寻找最多包含一个 0 的最长子数组。

解题思路

  1. 使用双指针(滑动窗口),维护窗口内最多包含一个 0
  2. 当窗口内的 0 超过 1 个时,移动左指针 left 直到窗口内 0 的数量恢复为 1。
  3. 记录窗口的最大长度,最终返回 maxLen - 1,因为必须删除一个元素(即使数组全是 1,我们仍然需要删掉一个)。

代码实现

def longestSubarray(nums):
    left = 0
    zero_count = 0
    max_len = 0
    
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1
        
        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len - 1  # 必须删除一个元素

复杂度分析

  • 时间复杂度:O(n),遍历数组一次,每个元素最多进出窗口一次。
  • 空间复杂度:O(1),只使用了常数额外空间。

示例

示例 1
nums = [1,1,0,1,1,1]
print(longestSubarray(nums))  # 输出: 5

解释:

  • 删除 0 后,最长的 1 子数组是 [1,1,1,1,1],长度为 5
示例 2
nums = [0,0,0]
print(longestSubarray(nums))  # 输出: 0

解释:

  • 无法形成全 1 的子数组,因此返回 0

这个方法高效且直观,适用于处理大规模数据。


http://www.kler.cn/a/585980.html

相关文章:

  • 将docker images导入crictl images
  • 基于腾讯云高性能HAI-CPU的跨境电商客服助手全链路解析
  • uniapp页面跳转带参数获取,需要注意在小程序和web下是不一样的
  • 网络爬虫相关
  • DeepLabv3+改进10:在主干网络中添加LSKBlock|动态调整其大型空间感受野,助力小目标识别
  • element-plus中Autocomplete自动补全输入框组件的使用
  • 硬件工程师入门教程(四)
  • linux ptrace 图文详解(二) PTRACE_TRACEME 跟踪程序
  • 解决Docker Desktop中ext4.vhdx文件过大的问题
  • 【Java 进阶实战】一 学习成果检验
  • 《大语言模型》学习笔记(一)
  • 初探大模型开发:使用 LangChain 和 DeepSeek 构建简单 Demo
  • Apache Doris中都用了哪些开发语言,编译过程中用到了哪些编译器,以及用到了哪些成熟的技术框架
  • 支持Linux、鸿蒙的工业AIOT智能终端在钢铁厂的应用
  • JavaScript性能优化实战:从8s到0.8s的极致提升
  • 钉钉(excel)能让表格中不是‘北京’的字符串自动加亮显示(方便查看)以及隔行填充严颜色是斑马色(方便查看)嘛
  • Vue 3 事件总线详解:构建组件间高效通信的桥梁
  • FPGA初级项目10——基于SPI的DAC芯片进行数模转换
  • Vlog 片头制作
  • Excel 数据转换为SQL语句