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

【LeetCode热题100总结】239. 滑动窗口最大值

题目描述

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值


[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2:
输入:nums = [1], k = 1
输出:[1]

提示:

1 <= nums.length <= 10^5
-104 <= nums[i] <= 10^4
1 <= k <= nums.length

以下参考力扣官方题解:
链接:https://leetcode.cn/problems/sliding-window-maximum/solutions/543426/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

相关标签

队列、滑动窗口、单调队列、堆(优先队列)

解题思路

对于每个滑动窗口,可以使用 O ( k ) O(k) O(k)的时间遍历每个元素,找到最大值。对于长度为 n 的数组 nums,窗口的数量为 n-k+1,因此算法的时间复杂度为 O ( ( n − k + 1 ) k ) = O ( n k ) O((n-k+1)k)=O(nk) O((nk+1)k)=O(nk),会超出时间限制,需要进行一些优化。可以想到,对于两个相邻(只差一个位置)的滑动窗口,共用着 k-1 个元素,只有一个元素是变化的,可以根据这个特点进行优化。

解法1:优先队列

对于最大值,可以想到一种非常合适的数据结构,优先队列(堆),其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

初始时,将数组的前k个元素放入优先队列中。每当向右移动窗口时,可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能不在滑动窗口中,而是出现在滑动窗口左边界的左侧。因此当我们继续向右移动窗口时这个值就永远不可能出现在滑动窗口中了,我们可以将其从优先队列中删除。

我们不断地移除堆顶元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素和滑动窗口的位置关系,我们可以在有限队列中存储二元组 ( n u m , i n d e x ) (num, index) num,index,表示元素 num 在数组中的下标为 index

code

class Solution:def maxSlidingWindow(self, nums:List[int], k:int) -> List[int]:n = len(nums)# python 默认的优先队列是小根堆q = [(-nums[i], i) for i in range(k)]heapq.heapify(q)	ans = [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] <= i-k:heapq.heappop(q)ans.append(-q[0][0])return ans

Python的heapq库是用于实现堆(优先队列)算法的库。它提供了一些函数来操作堆结构,如push、pop、heapify等。

heapq.heapify(q):将列表heap原地转换为一个堆。
heapq.heappush(heap, item:将元素item推入堆heap上。
heapq.heappop(q):从堆heap中弹出并返回最小的元素。

复杂度分析:

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),其中n数数组 nums 的长度。在最坏情况下数组的元素单调递增,那么最终优先队列中包含了所有元素,没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O ( n ) O(n) O(n),因此总时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 空间复杂度: O ( n ) O(n) O(n),即优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的空间,只计算额外的空间使用。

解法2:单调队列

由于我们需要求出的是滑动窗口的最大值,如果当前的滑动窗口中有两个下标i 和j,其中i 在 j的坐标,并且i 对应的元素不大于 j 对应的元素。那么当滑动窗口向右移动时,只要i 还在窗口中,那么j 一定也还在窗口中。因此i对应的元素一定不会是窗口中的最大值了,可以将其永久移除。

因此可以使用一个队列存储所有还没有被移除的下标,在队列中这些下标按照从小到大的顺序被存储,并且在数组nums中对应的值是严格单调递减的。

当窗口向右移动时,为了保持队列的性质,会不断将新的元素和队尾的元素相比较,如果前者大于等于后者,那么队尾的元素就可以被永久移除,弹出队列。不断进行此操作,知道队列为空或新元素小于队尾元素。

由于队列中下标对应的元素是严格单减的,因此队首下标对应的元素就是滑动窗口中的最大值。此时最大值可能在窗口左边界的左侧,因此还需要不断从队首弹出元素,直到队首元素在窗口中。

为了科研同时弹出队首和队尾的元素,需要使用双端队列。满足这种单调性的双端队列一般称为单调队列

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)q = collections.deque()for i in range(k):while q and nums[i] >= nums[q[-1]]:q.pop()q.append(i)ans = [nums[q[0]]]for i in range(k, n):while q and nums[i] >= nums[q[-1]]:q.pop()q.append(i)while q[0] <= i - k:q.popleft()ans.append(nums[q[0]])return ans

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)。每个下标恰好被放入队列一次,并且最多被弹出队列一次。
  • 空间复杂度:这里使用的数据结构是双向的,因此不断从队首弹出元素保证了队列中最多不会有超过 k+1 个元素,因此队列使用的空间为 O ( k ) O(k) O(k)

解法3: 分块 + 预处理

可以将数组nums从左到右按照k个一组进行分组,最后一组中元素的数量可能会不足k个。如果希望求出nums[i]nums[i+k-1]的最大值就会有两种情况:

  • 如果 i 是 k 的倍数,那么 nums[i] 到 nums[i+k-1] 恰好是一个分组。只要预处理出每个分组中的最大值即可;
  • 如果 i 不是 k 的备注,那么会跨越两个分组,占有第一个分组的后缀以及第二个分组的前缀。假设 j 是 k 的倍数,并且 i < j <= j+k-1,那么 nums[i]~nums[j-1]就是第一个分组的后缀,nums[j] 到 nums[i+k-1] 就是第二个分组的前缀。如果预处理出每个分组中的前缀最大值和后缀最大值,也可以在 O(1) 的时间得到答案。

prefixMax [ I ] \textit{prefixMax}[I] prefixMax[I]表示下标 i 对应的分组中,以 i 结尾的前缀最大值; suffixMax [ i ] \textit{suffixMax}[i] suffixMax[i] 表示下标 i 对应的分组中,以 i 开始的后缀最大值。它们分别满足如下的递推式

prefixMax [ i ] = { nums [ i ] , i 是  k 的倍数 max ⁡ { prefixMax [ i − 1 ] , nums [ i ] } , i 不是  k 的倍数 \textit{prefixMax}[i]=\begin{cases} \textit{nums}[i], & \quad i ~是~ k ~的倍数 \\ \max\{ \textit{prefixMax}[i-1], \textit{nums}[i] \}, & \quad i ~不是~ k ~的倍数 \end{cases} prefixMax[i]={nums[i],max{prefixMax[i1],nums[i]},i  k 的倍数i 不是 k 的倍数

以及

suffixMax [ i ] = { nums [ i ] , i + 1 是  k 的倍数 max ⁡ { suffixMax [ i + 1 ] , nums [ i ] } , i + 1 不是  k 的倍数 \textit{suffixMax}[i]=\begin{cases} \textit{nums}[i], & \quad i+1 ~是~ k ~的倍数 \\ \max\{ \textit{suffixMax}[i+1], \textit{nums}[i] \}, & \quad i+1 ~不是~ k ~的倍数 \end{cases} suffixMax[i]={nums[i],max{suffixMax[i+1],nums[i]},i+1  k 的倍数i+1 不是 k 的倍数

需要注意在递推 suffixMax [ i ] \textit{suffixMax}[i] suffixMax[i] 时需要考虑到边界条件 suffixMax [ n − 1 ] = nums [ n − 1 ] \textit{suffixMax}[n-1]=\textit{nums}[n-1] suffixMax[n1]=nums[n1],而在递推 prefixMax [ I ] \textit{prefixMax}[I] prefixMax[I] 时的边界条件 prefixMax [ 0 ] = nums [ 0 ] \textit{prefixMax}[0]=\textit{nums}[0] prefixMax[0]=nums[0] 恰好包含在递推式的第一种情况中,因此无需特殊考虑。

在预处理完成之后,对于 nums [ I ] \textit{nums}[I] nums[I] nums [ i + k − 1 ] \textit{nums}[i+k-1] nums[i+k1] 的所有元素,如果 i 不是 k 的倍数,那么窗口中的最大值为 suffixMax [ I ] \textit{suffixMax}[I] suffixMax[I] prefixMax [ i + k − 1 ] \textit{prefixMax}[i+k-1] prefixMax[i+k1] 中的较大值;如果 i 是 k 的倍数,那么此时窗口恰好对应一整个分组, suffixMax [ I ] \textit{suffixMax}[I] suffixMax[I] prefixMax [ i + k − 1 ] \textit{prefixMax}[i+k-1] prefixMax[i+k1] 都等于分组中的最大值,因此无论窗口属于哪一种情况,

suffixMax [ i ] , prefixMax [ i + k − 1 ] } \textit{suffixMax}[i], \textit{prefixMax}[i+k-1] \big\} suffixMax[i],prefixMax[i+k1]}即为答案。

此方法和稀疏表(Sparse Table)很类似。

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)prefixMax, suffixMax = [0] * n, [0] * nfor i in range(n):if i % k == 0:prefixMax[i] = nums[i]else:prefixMax[i] = max(prefixMax[i - 1], nums[i])for i in range(n - 1, -1, -1):if i == n - 1 or (i + 1) % k == 0:suffixMax[i] = nums[i]else:suffixMax[i] = max(suffixMax[i + 1], nums[i])ans = [max(suffixMax[i], prefixMax[i + k - 1]) for i in range(n - k + 1)]return ans

复杂度分析

  • 时间复杂度:O(n);
  • 空间复杂度:存储prefixMax和suffixMax需要的空间。

评论区一个很好的示例:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

相关文章:

【LeetCode热题100总结】239. 滑动窗口最大值

题目描述 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1&#xff1a; 输入&#xff1a;nums [1,3,-1,-3,5,3,6,7]…...

【YOLOv9改进[Conv]】使用YOLOv10的空间通道解耦下采样SCDown模块替换部分CONv的实践 + 含全部代码和详细修改内容

本文将使用YOLOv10的空间通道解耦下采样SCDown模块替换部分CONv的实践 ,文中含全部代码和详细修改内容。 目录 一 YOLOv10 1 空间通道解耦下采样 2 可视化...

简单小游戏制作

控制台基础设置 //隐藏光标 Console.CursorVisible false; //通过两个变量来存储舞台的大小 int w 50; int h 30; //设置舞台&#xff08;控制台&#xff09;的大小 Console.SetWindowSize(w, h); Console.SetBufferSize(w, h);多个场景 int nowSceneID 1; while (true) …...

Delphi

Delphi&#xff0c;是美国 Borland&#xff08;宝兰&#xff09;公司於 1995 年开发在 Windows 平台下的快速应用程式开发工具 (Rapid Application Development&#xff0c;简称 RAD)&#xff0c;它的前身是在 DOS 下的产品 Borland Turbo Pascal。&#xff08;非开源软件&…...

Linux的shell脚本中的比大小

如果要将 -le 换成相反的&#xff08;即“大于”&#xff09;&#xff0c;你应该使用 -gt&#xff08;greater than&#xff09;。 所以&#xff0c;-le 的相反比较是 -gt。 但如果你想要一个包含“大于”和“不等于”的比较&#xff08;即“大于”&#xff09;&#xff0c;那…...

每日复盘-20240603

20240603 六日涨幅最大: ------1--------300637--------- 扬帆新材 五日涨幅最大: ------1--------300637--------- 扬帆新材 四日涨幅最大: ------1--------301306--------- 西测测试 三日涨幅最大: ------1--------301306--------- 西测测试 二日涨幅最大: ------1--------30…...

adb server version (22000) doesn‘t match this client (41); killing...

参考链接: adb server version (31) doesn’t match this client (41); killing… 解决此问题 电脑安装了360手机助手占用了adb的端口引起的。因为套接字的唯一性&#xff08;一个套接字只能由 协议/网络地址/端口号 唯一确定 &#xff09;&#xff0c;一个电脑只能有一个程序…...

如何使用 Connector API 将数据提取到 Elasticsearch Serverless 中

作者&#xff1a;来自 Elastic Jedr Blaszyk Elasticsearch 支持一系列摄取方法。 其中之一是 Elastic Connectors&#xff0c;它将 SQL 数据库或 SharePoint Online 等外部数据源与 Elasticsearch 索引同步。 连接器对于在现有数据之上构建强大的搜索体验特别有用。 例如&…...

体育赛事直播系统开发源码搭建

随着体育产业的蓬勃发展&#xff0c;体育赛事直播已成为广大观众获取赛事信息的重要途径。为了满足观众日益增长的需求&#xff0c;开发一套专业的体育赛事直播系统成为当务之急。本文将围绕体育赛事直播系统开发源码搭建进行深入探讨&#xff0c;从技术选型、系统架构、安全防…...

使用Jmeter进行性能测试

学习视频 B站UP主&#xff1a;白月黑羽编程 目录 Jmeter的下载 Jmeter界面 Jmeter操作 线程组与HTTP请求 测试一个请求 解决响应数据中 中文乱码的问题 HTTP请求默认值 录制网站流量 添加录制控制器 添加HTTP代理服务器 在浏览器配置代理 进行录制 模拟间隔时间 …...

AI技术的发展,会让你工作轻松吗

这两年&#xff0c;人工智能技术迅猛发展&#xff0c;AI产品层出不穷&#xff0c;尤其大语言模型&#xff08;LLM&#xff09;的爆火&#xff0c;许多人担心自己的工作会被AI取代。然而&#xff0c;如果AI技术发展到极致&#xff0c;再加上其他科学技术的高度发展&#xff0c;我…...

Spring-DI入门案例

黑马程序员SSM框架教程 文章目录 一、DI入门案例思路分析二、实现步骤2.1 删除service中使用new形式创建的Dao对象2.2 提供以来对象对应的setter方法2.3 配置service与到之间的关系 一、DI入门案例思路分析 基于IoC管理bean&#xff08;上个案例已经实现&#xff09;service中…...

ubuntu18.04 报错:fatal error: execution

一、问题描述 在ubuntu18.04上编译Faster-lio 报错&#xff1a; fatal error: execution: 没有那个文件或目录#include <execution> 二、解决方法 需要将g编译器更新到9.0 sudo add-apt-repository ppa:ubuntu-toolchain-r/test sudo apt update sudo apt install g…...

开源大模型与大模型api的使用优缺点

开源大模型和大模型 API 都是人工智能领域中的重要概念&#xff0c;它们各自有一些优缺点。 开源大模型&#xff1a; 优点&#xff1a; 免费使用&#xff1a; 大多数开源大模型是免费提供的&#xff0c;任何人都可以访问和使用这些模型&#xff0c;降低了使用门槛。可定制性…...

小红书前端2轮面试期望22K,全程问低代码设计

一面&#xff08;通过&#xff09; 1、好&#xff0c;那我们开始把&#xff0c;先简单介绍一下自己的一个经历&#xff0c;以及自己有亮点的项目&#xff1f;balabala 2、你可以这样介绍&#xff1a;在这里边主要负责哪几个项目&#xff0c;哪些项目是比较有亮点的&#xff0…...

HIK录像机GB28181对接相机不在线问题随笔

一、问题现象 【设备信息】型号&#xff1a;DS-8664N-I16-V3 V4.63.000 build 230412 【问题现象】HIK录像机使用GB28181对接异常相机无法正常上线&#xff0c;对接HIK相机可以正常上线。 【现场拓扑】现场拓扑如下 NVR侧使用固定公网IP地址。IPC侧使用家用宽带的方式&…...

stm32-DMA转运数据

在配置前要记得先定义一下DMA转运的源端数组和目标数组两个数组哦。 接下来我们就开始准备配置吧 配置 初始化 1.RCC开启时钟&#xff08;开启DMA的时钟&#xff09; void RCC_AHBPeriphClockCmd(uint32_t RCC_AHBPeriph, FunctionalState NewState) 作用&#xff1a;开启时…...

Java编程常见问题汇总一

系列文章目录 文章目录 系列文章目录前言一、字符串连接误用二、错误的使用StringBuffer三、测试字符串相等性四、数字转换成字符串五、利用不可变对象(Immutable) 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分…...

用Unityhub安装unity2018.3.0和vuforia

打开下载网址 https://unity.cn/releases/full/2018 选择2018.3.x 找到2018.3.0后&#xff0c;点击从UnityHub下载 然后unityhub会弹出安装界面 只勾选这两个&#xff0c;其余的全部取消勾选&#xff0c;默认勾选上的也取消掉&#xff0c;然后点击安装...

智汇云舟与芯瞳完成兼容适配,共建国产化生态体系

近日&#xff0c;智汇云舟的视频孪生系列产品和时空大数据系列产品已完成与芯瞳半导体技术&#xff08;山东&#xff09;有限公司GPU产品GB2062/GB2064/CQ2040/CQ2040 MXM/CQ2040 MD的相互兼容性测试认证。双方产品经过严格测试&#xff0c;已完成兼容适配&#xff0c;具备良好…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...