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

每日一题——滑动窗口的最大值

滑动窗口的最大值

题目链接


暴力解法

最容易想到的当然还是通过两层循环来暴力求解:一层循环用来移动窗口,一层循环用来在窗口内找到最大值。这种做法的时间复杂度为O(kN),会超出时间限制,因此,我们要找到更加高效的方法。

单调队列

注:这种解法建立在单调队列的基础之上,而单调队列是双端队列的特殊形式,如果对单调队列和双端队列还不太了解,建议先看看👉详解单调队列

由于我们要求的是滑动窗口的最大值,那我们不妨先做一个假设:如果当前的滑动窗口中有两个下标ij,其中**ij的左侧(i < j,并且i对应的元素不大于j对应的元素(nums[i] <= nums[j])**。

那么我们就可以得到这样一个结论:只要下标i所代表的元素nums[j]还在窗口中,那么下标j所对应的元素nums[j]也一定在窗口中,且**nums[i]一定不会是最大值**,也就不会对答案造成影响,我们也就可以将其直接删除

也可以用一句话来概括:

如果一个数据val要进入窗口,那他窗口内所有比它小或等于它的的数都不会对答案造成影响

我们可以用一个队列来存储这些还没有被移除的元素的下标,同时确保从队头到队尾,这些下标是从小到大排列的(保证数据的愿所有顺序),而下标所代表的值是递减排列的,这样队头元素就是滑动窗口的最大值了。

每当窗口向右滑动一个元素,就会有一个新的元素入队。在这个元素入队之前,由于我们要确保队列的单调递减性,因此当队列不为空并且队尾元素小于或等于新的元素时就要通过循环删除这些不会对结果造成影响的元素,最后再把这个元素的下标插入队列。

需要注意:当窗口向右滑动时,最大值下标会离开窗口,永远不会在进入窗口,因此在窗口滑动的过程中,我们要不断比较队首元素的下标(最大值下标)和窗口最左侧的标(下次移动时离开窗口的元素下标),如果离开了窗口,就要将队首元素出队。

例如对于上图的示例:

实现代码

typedef struct DequeNode
{struct DequeNode* next;struct DequeNode* prev;int data;
}DQNode;typedef struct Deque
{DQNode* front;DQNode* tail;
}Deque;void DequeInit(Deque* pq)   //双端队列初始化
{assert(pq);pq->front = pq->tail = NULL;
}bool DequeEmpty(Deque* pq)  //双端队列判空
{assert(pq);return pq->front == NULL;
}void DequePushTail(Deque* pq, int val)  //队尾入队
{DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));newNode->data = val;newNode->next = NULL;newNode->prev = NULL;if (DequeEmpty(pq)){pq->front = pq->tail = newNode;}else{pq->tail->next = newNode;newNode->prev = pq->tail;pq->tail = newNode;}
}void DequePushFront(Deque* pq, int val) //队头入队
{DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));newNode->data = val;newNode->next = NULL;newNode->prev = NULL;if (DequeEmpty(pq)){pq->front = pq->tail = newNode;}else{newNode->next = pq->front;pq->front->prev = newNode;pq->front = newNode;}
}int DequePopFront(Deque* pq)    //队头出队
{assert(pq);assert(!DequeEmpty(pq));DQNode* temp = pq->front;int ret = temp->data;pq->front = pq->front->next;if (pq->front == NULL)pq->tail = NULL;elsepq->front->prev = NULL;free(temp);return ret;
}int DequePopTail(Deque* pq) //队尾出队
{assert(pq);assert(!DequeEmpty(pq));DQNode* temp = pq->tail;int ret = temp->data;pq->tail = pq->tail->prev;if (pq->tail == NULL)pq->front = NULL;elsepq->tail->next = NULL;free(temp);return ret;
}int DequeTail(Deque* pq)    //取队尾元素
{assert(pq);assert(!DequeEmpty(pq));return pq->tail->data;
}int DequeFront(Deque* pq)   //取队头元素
{assert(pq);assert(!DequeEmpty(pq));return pq->front->data;
}void DequeDestroy(Deque* pq)    //销毁双端队列
{while (!DequeEmpty(pq)){DQNode* temp = pq->front;pq->front = pq->front->next;free(temp);}free(pq);
}
//-------------------------------------双端队列基本功能实现-----------------------------------------------int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){*returnSize = numsSize - k + 1;int* ret = (int*)malloc(sizeof(int) * (*returnSize));Deque* DQ_Max = (Deque*)malloc(sizeof(Deque));  //用来记录最大值下标DequeInit(DQ_Max);	//初始化//先将数组前k个入队列,构建初始窗口for (int i=0; i<k; i++){//队列不为空且队尾元素小于或等于新元素,就将队尾元素删除//确保递减while (!DequeEmpty(DQ_Max) && nums[DequeTail(DQ_Max)] <= nums[i]){DequePopTail(DQ_Max);}DequePushTail (DQ_Max, i);	//将下标入队}ret[0] = nums[DequeFront(DQ_Max)];	//初始窗口的最大值就是队头下下标所代表的元素//再将后面剩余的元素下标入队for (int i=k; i<numsSize; i++){//删除不在窗口的下标while (!DequeEmpty(DQ_Max) && DequeFront(DQ_Max) <= i - k)DequePopFront(DQ_Max);//队列不为空且队尾元素小于新元素,就将队尾元素删除//确保非递增while (!DequeEmpty(DQ_Max) && nums[DequeTail(DQ_Max)] <= nums[i]){DequePopTail(DQ_Max);}DequePushTail (DQ_Max, i);//窗口最大值就是队头下下标所代表的元素ret[i - k + 1] = nums[DequeFront(DQ_Max)];}//销毁队列,释放内存DequeDestroy(DQ_Max);return ret;
}

相关文章:

每日一题——滑动窗口的最大值

滑动窗口的最大值 题目链接 暴力解法 最容易想到的当然还是通过两层循环来暴力求解&#xff1a;一层循环用来移动窗口&#xff0c;一层循环用来在窗口内找到最大值。这种做法的时间复杂度为O(kN)&#xff0c;会超出时间限制&#xff0c;因此&#xff0c;我们要找到更加高效的…...

【使用go开发区块链】之获取链上数据(03)

上篇文章&#xff0c;我们完成了数据库的连接&#xff0c;本章节&#xff0c;我们将完成ethclient的配置以及初始化 1、ethclient配置 1.1、安装go-ethereum 在命令行终端输入下面代码安装&#xff1a; go get github.com/ethereum/go-ethereum1.2、Ethclient配置 1.2.1、新…...

js 动态设置transformOrigin

transformOrigin属性用于指定元素变换的原点。 // 获取要设置的元素 const element document.getElementById(your-element-id);// 设置transformOrigin属性 element.style.transformOrigin 50% 50%; // 以元素中心为原点// 或者使用变量来设置 const x 0; // x坐标 const …...

docker使用tab无法自动补全命令

本文参考链接 一、安装bash-complete 在线安装 yum install -y bash-completion二、刷新文件 source /usr/share/bash-completion/completions/docker source /usr/share/bash-completion/bash_completion...

既然jmeter也能做接口自动化,为什么还需要pytest自己搭框架?

今天这篇文章呢&#xff0c;我会从以下几个方面来介绍&#xff1a; 1、首先介绍一下pytest框架 2、带大家安装Pytest框架 3、使用pytest框架时需要注意的点 4、pytest的运行方式 5、pytest框架中常用的插件 一、pytest框架介绍 pytest 是 python 的第三方单元测试框架&a…...

Objective-C获取变量类型的方法

在Objective-C中&#xff0c;要获取一个对象的类型&#xff0c;可以使用[object class]方法。这将返回一个Class对象&#xff0c;表示该对象的类型。 另外&#xff0c;typeid是C中的关键字&#xff0c;用于获取一个变量的类型信息。在Objective-C中&#xff0c;typeid并不适用于…...

相机可见区域,使用鼠标拖拽模型

知识点 向量射线检测坐标转换 思路 使用射线检测获取射线检测点与模型对象之间的偏移量 &#xff08;世界空间&#xff09;使用相机的坐标转换获取检测点与鼠标位置之间的偏移量 &#xff08;屏幕空间&#xff09;拖拽时&#xff0c;更新模型位置 代码示例 using UnityEng…...

Vue 2 与 Vue 3 的全面比较

Vue 2 与 Vue 3 的全面比较 1. 性能提升 Vue 3 的性能得到了显著提升。虚拟 DOM 已经重写&#xff0c;使补丁过程更快。 对比&#xff1a; Vue 3 使用了基于 Proxy 的新观察者机制&#xff0c;取代了 Vue 2 的基于 Object.defineProperty 的观察者。 Object.definePropert…...

Unity学习笔记--如何优雅简便地利用对象池生成游戏对象(进阶版)LRU + 对象池

前言 之前写过一篇关于对象池的文章&#xff0c;现在来看写的并不是很好&#xff0c;所以来考虑优化下。 现在来看一年前写的代码&#xff0c;越看越不能入目hhh Unity学习笔记–如何优雅简便地利用对象池生成游戏对象 前置知识 Unity学习笔记–使用 C# 开发一个 LRU 代码实…...

【Spring专题】Bean的声明周期流程图

前言 我向来不主张【通过源码】理解业务&#xff0c;因为每个人的能力有限&#xff0c;甚至可能会因为阅读错误导致出现理解上的偏差&#xff0c;所以我决定&#xff0c;还是先帮大家【开天眼】&#xff0c;先整体看看流程图&#xff0c;好知道&#xff0c;Spring在写源码的过…...

C++实现俄罗斯方块(源码+详解)

&#x1f442; Take me Hand Acoustic - Ccile Corbel - 单曲 - 网易云音乐 源码Debug工具 &#xff08;1&#xff09;cppreference.com &#xff08;主&#xff09; &#xff08;2&#xff09;必应 (bing.com) &#xff08;3&#xff09;GPT&#xff08;主&#xff09; &#…...

01:STM32点灯大师和蜂鸣器

目录 一:点亮1个LED 1:连接图 2:函数介绍 3:点灯代码 二:LED闪烁 1:函数介绍 2:闪烁代码 三:LED流水灯 1:连接图 2:函数介绍 3:流水灯代码 四:蜂鸣器 1:连接图 2:蜂鸣器代码 一:点亮1个LED 1:连接图 因为IO口与LED负极相连所以IO口输出低电频,点亮LED (采用的是低…...

linux pwn 基础知识

环境搭建 虚拟机安装 镜像下载网站为了避免环境问题建议 22.04 &#xff0c;20.04&#xff0c;18.04&#xff0c;16.04 等常见版本 ubuntu 虚拟机环境各准备一份。注意定期更新快照以防意外。虚拟机建议硬盘 256 G 以上&#xff0c;内存也尽量大一些。硬盘大小只是上界&#…...

Unity Poisson分布 【由ChatGPT生成】

Unity Poisson分布 【由ChatGPT生成】 前言项目Unity场景布置代码编写添加并设置脚本运行效果总结 前言 在Unity游戏开发中&#xff0c;数学和统计学的概念常常用于解决各种问题&#xff0c;从资源分配到游戏机制的设计。本文将探讨Poisson分布在Unity游戏开发中的实际应用和作…...

permission denied while trying to connect to the Docker daemon socket 错误

安装 docker 执行错误如下&#xff1a; $ docker pspermission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Get “http://%2Fvar%2Frun%2Fdocker.sock/v1.24/containers/json”: dial unix /var/run/docker.sock: connect:…...

pytorch nn.ModuleList和nn.Sequential的用法笔记

有部分内容转自: pytorch小记:nn.ModuleList和nn.Sequential的用法以及区别_慕思侣的博客-CSDN博客 但是有部分内容做了修改调整, 在构建网络的时候,pytorch有一些基础概念很重要,比如nn.Module,nn.ModuleList,nn.Sequential,这些类我们称为为容器(containers),可…...

SQL | 高级数据过滤

5-高级数据过滤 通过组合WHERE子句&#xff0c;建立功能更强的检索语句。 5.1-组合WHERE子句 前面写的都是单一条件下的WHERE子句&#xff0c;SQL语句允许给出多个WHERE子句来组合检索&#xff0c;这些WHERE子句通过AND子句或者OR子句进行连接。 操作符&#xff08;operato…...

ARM架构银河麒麟docker,源码编译安装GDAL

docker中安装依赖 sudo apt-get update sudo apt-get install build-essential autoconf automake libtool sudo apt-get install libproj-dev libgeos-dev libjson-c-dev libpng-dev libjpeg-dev sudo apt-get install python3-dev sudo apt-get install python3.11-dev去官网…...

(3)原神角色数据分析-3

绘图类 在名为“WRITEPHOT.py”的文件中&#xff0c;定义如下绘图方式&#xff0c;则在主页面(app.py)文件中&#xff0c;可通过如下方式调用&#xff1a; from WRITEPHOTO import WriteScatter,WriteFunnel,WriteBarData,WritePie,WriteLineBar 代码如下&#xff1a; "…...

skywalking日志收集

文章目录 一、介绍二、添加依赖三、修改日志配置1. 添加链路表示traceId2. 添加链路上下文3. 异步日志 四、收集链路日志 一、介绍 在上一篇文章skywalking全链路追踪中我们介绍了在微服务项目中使用skywalking进行服务调用链路的追踪。 本文在全链路追踪的基础上&#xff0c…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...