每日一题——滑动窗口的最大值
滑动窗口的最大值
- 题目描述
- 示例
- 说明
- 解题思路
- 双端队列的特点
- 实现步骤
- 代码实现（C语言）
- 代码解析
- 总结
题目描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size，找出所有滑动窗口里数值的最大值。
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 {4, 4, 6, 6, 6, 5}。
示例
示例 1
输入：
[2,3,4,2,6,2,5,1], 3
返回值：
[4, 4, 6, 6, 6, 5]
示例 2
输入：
[9,10,9,-7,-3,8,2,-6], 5
返回值：
[10, 10, 9, 8]
示例 3
输入：
[1, 2, 3, 4], 5
返回值：
[]
说明
- 如果滑动窗口的大小大于数组的长度或者大小为 0，则返回空数组。
解题思路
这个问题可以通过滑动窗口的方式解决，同时需要注意效率和空间复杂度。我们可以使用 双端队列（Deque） 来高效地解决这个问题。
双端队列的特点
- 双端队列可以在
O(1)的时间复杂度内从两端删除和添加元素。 - 通过双端队列，我们可以在滑动窗口内保持一个有序的队列，其中队列的前端始终是窗口中的最大值。
实现步骤
- 初始化双端队列：用于保存当前滑动窗口内的元素索引，队列保持单调递减的顺序，即队列中的元素从前到后的值是递减的。
- 遍历数组：每遍历到一个新的元素时：
- 移除不在窗口内的元素。
- 维护队列的递减性质，移除队列中比当前元素小的所有元素。
- 将当前元素的索引添加到队列中。
- 当窗口大小达到
size时，队列前端的元素就是当前窗口的最大值。
- 返回结果：每次更新窗口后，将最大值添加到结果数组中。
代码实现（C语言）
#include <stdio.h>
#include <stdlib.h>typedef struct {int *data; // 用于存储队列元素的数组int front; // 队列头int rear; // 队列尾
} Deque;// 创建一个空的双端队列
Deque* createDeque(int capacity) {Deque *dq = (Deque*)malloc(sizeof(Deque));dq->data = (int*)malloc(capacity * sizeof(int));dq->front = -1;dq->rear = -1;return dq;
}// 判断队列是否为空
int isEmpty(Deque *dq) {return dq->front == -1;
}// 判断队列是否已满
int isFull(Deque *dq) {return dq->rear == dq->front - 1;
}// 从队列前端删除元素
void popFront(Deque *dq) {if (!isEmpty(dq)) {dq->front++;if (dq->front > dq->rear) {dq->front = dq->rear = -1; // 队列空时重置}}
}// 从队列后端删除元素
void popBack(Deque *dq) {if (!isEmpty(dq)) {dq->rear--;if (dq->rear < dq->front) {dq->front = dq->rear = -1; // 队列空时重置}}
}// 从队列前端获取元素
int front(Deque *dq) {return dq->data[dq->front];
}// 向队列后端添加元素
void pushBack(Deque *dq, int value) {if (dq->front == -1) {dq->front = dq->rear = 0;} else {dq->rear++;}dq->data[dq->rear] = value;
}// 滑动窗口最大值的函数
int* maxSlidingWindow(int* nums, int numsSize, int size, int* returnSize) {int *result = (int*)malloc((numsSize - size + 1) * sizeof(int));*returnSize = 0;if (size == 0) {return result; // 如果窗口大小为0，返回空数组}Deque *dq = createDeque(numsSize); // 创建双端队列for (int i = 0; i < numsSize; ++i) {// 移除队列中超出窗口范围的元素if (!isEmpty(dq) && front(dq) < i - size + 1) {popFront(dq);}// 移除队列中比当前元素小的元素while (!isEmpty(dq) && nums[front(dq)] <= nums[i]) {popBack(dq);}// 添加当前元素到队列pushBack(dq, i);// 当窗口大小达到 size 时，记录当前窗口的最大值if (i >= size - 1) {result[(*returnSize)++] = nums[front(dq)];}}return result;
}// 测试函数
int main() {int nums[] = {2, 3, 4, 2, 6, 2, 5, 1};int size = 3;int returnSize = 0;int *result = maxSlidingWindow(nums, sizeof(nums) / sizeof(nums[0]), size, &returnSize);for (int i = 0; i < returnSize; ++i) {printf("%d ", result[i]);}free(result); // 释放结果数组return 0;
}
代码解析
-
初始化双端队列：
- 我们使用结构体
Deque来表示双端队列。队列包含一个动态分配的数组data来存储元素，以及front和rear来表示队列的前端和后端。 createDeque函数用于创建一个空的双端队列。popFront和popBack分别是从队列的前端和后端删除元素。pushBack是向队列后端添加元素。front函数返回队列前端的元素。
- 我们使用结构体
-
滑动窗口的最大值函数：
maxSlidingWindow函数是核心逻辑，接收一个数组、窗口大小和数组的大小，并返回一个数组，表示每个滑动窗口的最大值。- 使用双端队列来维护当前窗口的最大值。每次窗口滑动时，移除不再窗口范围内的元素，并维护队列的单调性，确保队列中的最大元素总是在队列的前端。
-
时间与空间复杂度：
- 时间复杂度：每个元素至多被添加和移除一次，所以时间复杂度是
O(n)，其中n是数组的长度。 - 空间复杂度：队列最多存储
n个元素，因此空间复杂度是O(n)。
- 时间复杂度：每个元素至多被添加和移除一次，所以时间复杂度是
总结
捣鼓了半天的数组和堆栈，结果发现实现不了，pop和push是最难的，所以还是要老老实实根据教程案例来学习，标新立异没必要。
相关文章：
每日一题——滑动窗口的最大值
滑动窗口的最大值 题目描述示例说明 解题思路双端队列的特点实现步骤代码实现（C语言）代码解析 总结 题目描述 给定一个长度为 n 的数组 num 和滑动窗口的大小 size，找出所有滑动窗口里数值的最大值。 例如，如果输入数组 {2, 3, …...
DeepSeek 的含金量还在上升
大家好啊，我是董董灿。 最近 DeepSeek 越来越火了。 网上有很多针对 DeepSeek 的推理测评，除此之外，也有很多人从技术的角度来探讨 DeepSeek 带给行业的影响。 比如今天就看到了一篇文章，探讨 DeepSeek 在使用 GPU 进行模型训练…...
list容器（详解）
list的介绍及使用（了解，后边细讲） 1.1 list的介绍（双向循环链表） https://cplusplus.com/reference/list/list/?kwlist（list文档介绍） 1. list是可以在常数范围内在任意位置进行插入和删除的序…...
FinRobot：一个使用大型语言模型的金融应用开源AI代理平台
“FinRobot: An Open-Source AI Agent Platform for Financial Applications using Large Language Models” 论文地址：https://arxiv.org/pdf/2405.14767 Github地址：https://github.com/AI4Finance-Foundation/FinRobot 摘要 在金融领域与AI社区间&a…...
【llm对话系统】大模型 Llama 源码分析之 LoRA 微调
1. 引言 微调 (Fine-tuning) 是将预训练大模型 (LLM) 应用于下游任务的常用方法。然而，直接微调大模型的所有参数通常需要大量的计算资源和内存。LoRA (Low-Rank Adaptation) 是一种高效的微调方法，它通过引入少量可训练参数，固定预训练模型的权重，从而在保持性能的同时大…...
为AI聊天工具添加一个知识系统 之86 详细设计之27 数据处理：ETL
本文要点 ETL 数据提取 作为 数据项目的起点。数据的整个三部曲--里程碑式的发展进程： ETL : 1分形 Type()-层次Broker / 2完形 Method() - 维度Delegate /3 整形 Class() - 容器 Agent 1变象。变象 脸谱Extractor - 缠度（物理 皮肤缠度…...
「全网最细 + 实战源码案例」设计模式——策略模式
核心思想 策略模式（Strategy Pattern）是一种行为型设计模式，用于定义一系列算法或策略，将它们封装成独立的类，并使它们可以相互替换，而不影响客户端的代码，提高代码的可维护性和扩展性。 结构 …...
框架与代码的形状
作为一个代码的设计者，我之前讨论过代码的形状，从“名字”出发，进行讨论。代码的形状：重构的方向-CSDN博客 从比喻的角度来看，名字似代码的血和肉，而框架则似代码的骨架。 猎豹和大象 在大自然中&…...
解决vscode扩展插件开发webview中的请求跨域问题
在webview中是无法发送跨域请求的，可以通过消息机制，在插件中发请求，然后将请求结果传递给webview 我的代码是基于vscode-webview-ui-toolkit-samples-vue来写的 webview vue组件中的代码示例 async function initData() {// 向插件发送消…...
junit5定制点
一、JUnit 5 自定义定制点是什么？ JUnit 5 提供了强大的扩展模型（Extension Model），允许开发者通过实现特定接口（如 BeforeEachCallback、ParameterResolver）自定义测试行为。这些接口称为定制点ÿ…...
)
基于SpringBoot的信息技术知识赛系统的设计与实现(源码+SQL脚本+LW+部署讲解等)
专注于大学生项目实战开发,讲解,毕业答疑辅导，欢迎高校老师/同行前辈交流合作✌。 技术范围：SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容：…...
【Rust自学】20.1. 最后的项目：单线程Web服务器
喜欢的话别忘了点赞、收藏加关注哦（加关注即可阅读全文），对接下来的教程有兴趣的可以关注专栏。谢谢喵！(･ω･) 20.1.1. 什么是TCP和HTTP Web 服务器涉及的两个主要协议是超文本传输协议(Hypertext T…...
LabVIEW涡轮诊断系统
一、项目背景与行业痛点 涡轮机械是发电厂、航空发动机、石油化工等领域的核心动力设备，其运行状态直接关系到生产安全与经济效益。据统计，涡轮故障导致的非计划停机可造成每小时数十万元的经济损失，且突发故障可能引发严重安全事故。传统人…...
想品客老师的第十天：类
类是一个优化js面向对象的工具 类的声明 //1、class User{}console.log(typeof User)//function//2、let Hdclass{}//其实跟1差不多class Stu{show(){}//注意这里不用加逗号，对象才加逗号get(){console.log(后盾人)}}let hdnew Stu()hd.get()//后盾人 类的原理 类…...
注解（Annotation）
注解（Annotation）在 Java 中可以用来简化类的使用，使得被注解的类能够被自动发现、自动创建并在需要的地方直接调用，而不需要手动创建实例。具体来说，注解是用来标识类、方法、字段等的，它们通常与一些框架…...
使用开源项目：pdf2docx，让PDF转换为Word
目录 1.安装python 2.安装 pdf2docx 3.使用 pdf2docx 转换 PDF 到 Word pdf2docx：GitCode - 全球开发者的开源社区,开源代码托管平台 环境：windows电脑 1.安装python Download Python | Python.org 最好下载3.8以上的版本 安装时记得选择上&#…...
编程AI深度实战：AI编程工具哪个好? Copilot vs Cursor vs Cody vs Supermaven vs Aider
Cursor自己可以看成一个IDE，而且有强大的RAG功能，这让它对你的意图感知非常厉害，可以精确补全，可以感受代码片段 Aider可以看作一个袖珍，灵活，强大的扳手，怎么用都行，可以放在脚本里调用，可以看代码，可以修改代码。相比Cursor而言，它感受的是文件级别，颗粒度有些不…...
如何安全地管理Spring Boot项目中的敏感配置信息
在开发Spring Boot应用时，我们经常需要处理一些敏感的配置信息，比如数据库密码、API密钥等。以下是一个最佳实践方案： 1. 创建配置文件 application.yml（版本控制） spring:datasource:url: ${MYSQL_URL:jdbc:mysql…...
为AI聊天工具添加一个知识系统 之77 详细设计之18 正则表达式 之5
本文要点 昨天讨论了 本项目（AI聊天工具添加一个知识系统）中正则表达式模板的设计中可能要考虑到的一些问题（讨论到的内容比较随意，暂时无法确定 那些考虑 是否 应该是正则表达式模板设计要考虑的以及 是否完整）。今天…...
Ubuntu下Tkinter绑定数字小键盘上的回车键（PySide6类似）
设计了一个tkinter程序，在Win下绑定回车键，直接绑定"<Return>"就可以使用主键盘和小键盘的回车键直接“提交”，到了ubuntu下就不行了。经过搜索，发现ubuntu下主键盘和数字小键盘的回车键，名称不一样。…...
安全实验作业
一 拓扑图 二 要求 1、R4为ISP，其上只能配置IP地址；R4与其他所有直连设备间均使用共有IP 2、R3-R5-R6-R7为MGRE环境，R3为中心站点； 3、整个OSPF环境IP基于172.16.0.0/16划分； 4、所有设备均可访问R4的环回&#x…...
NOTEPAD++编写abap
参考下面三个链接 Notepad ABAP代码高亮显示_notepad代码高亮颜色-CSDN博客 百度安全验证 ABAP Syntax Highlighting in Notepad Part 2 - SAP Community 最后XML文件看看你可以自己增加些新语法的高亮显示...
基于python的体育新闻数据可视化及分析
项目 ：北京冬奥会体育新闻数据可视化及分析 摘 要 随着社会的不断进步与发展，新时代下的网络媒体获取的信息也更加庞大和繁杂，相比于传统信息来源更加难以分析和辨别，造成了新时代媒体从业者撰写新闻的难度。在此背景下ÿ…...
)
C# 精炼题18道题(类,三木运算,Switch,计算器)
1.数组元素和 2.数组元素乘积 3.数组元素平均数 4.数组中最大值 5.数组中的偶数 6.数组中的阶乘 7.数组反转 8.字符串反转 9.回文字符串 10.检查回文 11.最小最大值 12.找素数 13.字符串中的最长无重复字符串 14.字符串去重 15.数组中计算两数之和 16.数字到字符…...
vue2语法速通
首先，git clone下来的项目要npm install下载依赖，如果是vue项目，运行通常npm run serve或者npm run dev vue速通一下 使用vite创建项目（较快） npm create vite 配置文件 src/ ├── assets/ # 存放…...
LabVIEW图片识别逆向建模系统
本文介绍了一个基于LabVIEW的图片识别逆向建模系统的开发过程。系统利用LabVIEW的强大视觉处理功能，通过二维图片快速生成对应的三维模型，不仅降低了逆向建模的技术门槛，还大幅提升了建模效率。 项目背景 在传统的逆向建模过程中…...
idea隐藏无关文件
idea隐藏无关文件 如果你想隐藏某些特定类型的文件（例如 .log 文件或 .tmp 文件），可以通过以下步骤设置： 打开设置 在菜单栏中选择 File > Settings（Windows/Linux）或 IntelliJ IDEA > Preference…...
Google C++ Style / 谷歌C++开源风格
文章目录 前言1. 头文件1.1 自给自足的头文件1.2 #define 防护符1.3 导入你的依赖1.4 前向声明1.5 内联函数1.6 #include 的路径及顺序 2. 作用域2.1 命名空间2.2 内部链接2.3 非成员函数、静态成员函数和全局函数2.4 局部变量2.5 静态和全局变量2.6 thread_local 变量 3. 类3.…...
猫眼Java开发面试题及参考答案（上）
详细介绍项目，像项目中如何用 Redis，用到 Redis 哪些数据类型，项目中遇到哪些问题，怎么解决的 在我参与的一个电商项目中，Redis 发挥了至关重要的作用。这个电商项目主要是为用户提供商品浏览、购物车管理、订单处理等一系列功能。 在项目中使用 Redis 主要是为了提升系统…...
CNN的各种知识点（五）：平均精度均值（mean Average Precision, mAP）
平均精度均值（mean Average Precision, mAP） 1. 平均精度均值（mean Average Precision, mAP）概念：计算步骤：具体例子：重要说明：典型值范围： 总结： 1. 平均精度…...
)
8.原型模式(Prototype)
动机 在软件系统中，经常面临着某些结构复杂的对象的创建工作；由于需求的变化，这些对象经常面临着剧烈的变化，但是它们却拥有比较稳定一致的接口。 之前的工厂方法和抽象工厂将抽象基类和具体的实现分开。原型模式也差不多&#…...
DeepSeek-R1：开源机器人智能控制系统的革命性突破
目录 引言 一、DeepSeek-R1 的概述 1.1 什么是 DeepSeek-R1？ 1.2 DeepSeek-R1 的定位 二、DeepSeek-R1 的核心特性 2.1 实时控制能力 2.2 多传感器融合 2.3 路径规划与导航 2.4 人工智能集成 2.5 开源与模块化设计 2.6 跨平台支持 三、DeepSeek-R1 的技术…...
网络安全学习 day5
状态检测和会话技术 状态检测以 “ 数据流量 ” 为单位来对报文进行检测和转发。即对一条流量的第一个报文进行包过滤规 则检查，并将判断结果作为这条流量的 “ 状态 ” 记录下来 。对于该条流量的后续报文，直接根据这个 “ 状态 ”来判断是否转发还是…...
[leetcode·回溯算法]回溯算法解题套路框架
本文参考labuladong算法笔记[回溯算法解题套路框架 | labuladong 的算法笔记] 本文解决几个问题： 回溯算法是什么？解决回溯算法相关的问题有什么技巧？如何学习回溯算法？回溯算法代码是否有规律可循？ 其实回溯算法和我…...
【怎么用系列】短视频戒除—1—对推荐算法进行干扰
如今推荐算法已经渗透到人们生活的方方面面，尤其是抖音等短视频核心就是推荐算法。 【短视频的危害】 1> 会让人变笨，慢慢让人丧失注意力与专注力 2> 让人丧失阅读长文的能力 3> 让人沉浸在一个又一个快感与嗨点当中。当我们刷短视频时&#x…...
【deepseek实战】绿色好用，不断网
前言 最佳deepseek火热网络，我也开发一款windows的电脑端，接入了deepseek，基本是复刻了网页端，还加入一些特色功能。 助力国内AI，发出自己的热量 说一下开发过程和内容的使用吧。 目录 一、介绍 二、具体工作 1.1、引…...
kali下Docker详细安装、docker-compose安装
目录 一、kali下docker安装 1. 更换apt源 2.安装docker 3.配置国内镜像加速器 4.利用docker运行靶场环境 二、docker-compose安装 1.下载docker-compose文件 2.将下载的文件复制到指定位置 3.赋予执行权限 4.利用docker-compose运行靶场环境 一、kali下docker安装 1.…...
Spring理论知识（Ⅴ）——Spring Web模块
Spring的组成 Spring由20个核心依赖组成，这20个核心依赖可以分为6个核心模块 Spring Web模块简介 众所周知，Java目前最大的一个用途就是作为Web应用的服务端（Java Web） Spring又是JavaEE中使用最广泛的开发框架࿰…...
图书管理系统 Axios 源码__新增图书
目录 功能介绍 核心代码解析 源码：新增图书功能 总结 本项目基于 HTML、Bootstrap、JavaScript 和 Axios 开发，实现了图书的增删改查功能。以下是新增图书的功能实现，适合前端开发学习和项目实践。 功能介绍 用户可以通过 模态框…...
】从计算机基础到HTML开发：Web开发的第一步)
【学术投稿-2025年计算机视觉研究进展与应用国际学术会议 (ACVRA 2025)】从计算机基础到HTML开发：Web开发的第一步
会议官网：www.acvra.org 简介 2025年计算机视觉研究进展与应用（ACVRA 2025）将于2025年2月28-3月2日在中国广州召开，将汇聚世界各地的顶尖学者、研究人员和行业专家，聚焦计算机视觉领域的最新研究动态与应用成就。本次…...
Med-R2：基于循证医学的检索推理框架：提升大语言模型医疗问答能力的新方法
Med-R2 : Crafting Trustworthy LLM Physicians through Retrieval and Reasoning of Evidence-Based Medicine Med-R2框架Why - 这个研究要解决什么现实问题What - 核心发现或论点是什么How - 1. 前人研究的局限性How - 2. 你的创新方法/视角How - 3. 关键数据支持How - 4. 可…...
Docker入门篇（Docker基础概念与Linux安装教程）
目录 一、什么是Docker、有什么作用 二、Docker与虚拟机(对比) 三、Docker基础概念 四、CentOS安装Docker 一、从零认识Docker、有什么作用 1.项目部署可能的问题： 大型项目组件较多，运行环境也较为复杂，部署时会碰到一些问题࿱…...
完美世界C++游戏开发面试题及参考答案
堆栈数据结构有什么区别，举例说明 栈（Stack）和堆（Heap）是两种不同的数据结构，它们在多个方面存在显著区别： 存储方式 栈：栈是一种后进先出（LIFO）的数据结构，它的存储空间是连续的。栈由系统自动分配和释放，用于存储函数调用时的局部变量、函数参数、返回地址等信息…...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】2.21 随机数生成：梅森旋转算法的工程实现
2.21 随机数生成：梅森旋转算法的工程实现 目录 #mermaid-svg-J92AWLtQsj9ys1z6 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-J92AWLtQsj9ys1z6 .error-icon{fill:#552222;}#mermaid-svg-J92AWLtQsj9y…...
空间复杂度-一次遍历双指针)
LeetCode 0922.按奇偶排序数组 II：O(1)空间复杂度-一次遍历双指针
【LetMeFly】922.按奇偶排序数组 II：O(1)空间复杂度-一次遍历双指针 力扣题目链接：https://leetcode.cn/problems/sort-array-by-parity-ii/ 给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。 对数组进…...
VSCode设置内容字体大小
1、打开VSCode软件，点击左下角的“图标”，选择“Setting”。 在命令面板中的Font Size处选择适合自己的字体大小。 2、对比Font Size值为14与20下的字体大小。...
【蓝桥杯】日志统计
日志统计（编程题）https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53 题目 日志统计(编程题) 讲解 这个讲解感觉比较通俗易懂。 蓝桥杯2018年省赛B组08（c/c）日…...
)
九. Redis 持久化-AOF(详细讲解说明，一个配置一个说明分析，步步讲解到位 2)
九. Redis 持久化-AOF(详细讲解说明，一个配置一个说明分析，步步讲解到位 2) 文章目录 九. Redis 持久化-AOF(详细讲解说明，一个配置一个说明分析，步步讲解到位 2)1. Redis 持久化 AOF 概述2. AOF 持久化流程3. AOF 的配置4. AOF 启…...
蓝桥杯备赛题目练习（一）
一. 口算练习题 ## 题目描述 王老师正在教简单算术运算。细心的王老师收集了 i 道学生经常做错的口算题，并且想整理编写成一份练习。 编排这些题目是一件繁琐的事情，为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量，比…...
【Linux探索学习】第二十八弹——信号（下）：信号在内核中的处理及信号捕捉详解
Linux学习笔记： https://blog.csdn.net/2301_80220607/category_12805278.html?spm1001.2014.3001.5482 前言： 在前面我们已经学习了有关信号的一些基本的知识点，包括：信号的概念、信号产生和信号处理等，今天我们重…...