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

LeetCode Hot100之十:239.滑动窗口最大值

题目

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

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

在这里插入图片描述

提示:

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

思路

如果暴力做法,就是维护一个长度为k的数组,没移动时先遍历该数组,把最大值找出来。然后每移动一次,如果右边新加入的数>原最大值,则更新最大值。如果左边移走的数就是最大值,那么需要遍历此时移动后的数组,找出最大值。这个找出最大值的过程为O(k)。移动整体窗口的过程是O(n),合起来就是O(nk),会超出时间限制。因为移动整体窗口的过程是省略不了的,我们只能考虑如何将找出最大值的O(k)降为O(1)。

我们观察滑动窗口,如果此时滑动窗口中只有两个下标i和j,且i<j,nums[i]>=nums[j],那么只要i还在窗口内,那么j也一定还在窗口内。且nums[i]一定是窗口中的最大值,我们便不用再去遍历整个窗口了。如果我们以这个性质为出发点,维护一个严格单调递减的,下标从小到大的队列。即队列里存储的是下标,但是值是严格单调递减的。那么就相当于队列里存储的是原数组第一大元素的下标,原数组第二大元素的下标,原数组第三大元素的下标……。

当向右滑动,遍历到一个新元素now时,我们

  1. 首先需要判断now是否大于队列末尾的第k大元素klast。
    • 如果now>klast,那么意味着队列的元素,谁是第几大需要重新定义,于是只要队列不为空,我们便将now与队列末尾的元素last一个个比较,如果now大于last,就将last踢出队列,直到遇到一个比now大的元素,再将now插入到队列末尾(因为那些被踢掉的last永远不可能是答案,队列没有维护它们的必要)。
    • 如果now<klast,那么直接将now插入到队列末尾即可。
  2. 其次,我们再判断向右滑动时是否会导致队首,即原数组第一大元素滑出队列,因为队列中存储的是在原数组的下标,那么我们只需要判断这个队首元素是否>i-k即可。

java代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len = nums.length;Deque<Integer> deque = new LinkedList<>();int[] ans = new int[len-k+1];for(int i=0;i<k;i++){while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);}ans[0]=nums[deque.peekFirst()];for(int i=k;i<len;i++){while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);if(deque.peekFirst()<=i-k){deque.pollFirst();}ans[i-k+1]=nums[deque.peekFirst()];}return ans;
}
}

效率分析

28ms,击败80.23%使用 Java 的用户。没必要再优化了。

相关文章:

LeetCode Hot100之十:239.滑动窗口最大值

题目 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 提示&#xff1a; 1 < nums.length < 10^5 -10^4 < nums[i…...

x264、x265、OpenH264 简要对比

一&#xff1a; x264、x265、OpenH264&#xff0c;都是开源代码库&#xff1b;二&#xff1a; H264(MPEG-4/AVC)、H265(HEVC)&#xff0c;是视频编码格式。是视频标准&#xff1b; H264(MPEG-4/AVC) 简称: H264 或 AVC&#xff1b; H265(HEVC) 简称: H265 …...

二维码智慧门牌管理系统升级解决方案:门牌聚合,让管理更便捷!

文章目录 前言一、传统门牌管理系统的瓶颈二、地图门牌聚合展示的优势三、地图门牌聚合展示的实现方法四、智慧门牌管理系统的未来发展 前言 随着城市的发展和建设&#xff0c;对于地址信息的管理变得越来越重要。而智慧门牌管理系统作为管理地址信息的重要工具&#xff0c;其…...

物联网AI MicroPython学习之语法UART通用异步通信

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; UART 介绍 模块功能: UART通过串行异步收发通信 接口说明 UART - 构建UART对象 函数原型&#xff1a;UART(id, baudrate&#xff0c;bits, parity&#xff0c;stop, tx, rx)参数说明&#xff1a; 参数类…...

Git企业开发级讲解(四)

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、理解分⽀二、创建分支三、切换分⽀四、合并分⽀五、删除分⽀六、合并冲突七、分⽀管理策略…...

pytorch 安装 2023年

pytorch网址&#xff1a;https://pytorch.org/get-started/locally/ conda install pytorch torchvision torchaudio pytorch-cuda11.8 -c pytorch -c nvidia我在自己电脑上用这个pip命令完全安装不了&#xff0c;只能用conda安装。复制上面提供的命令&#xff0c;在cmd中直接运…...

人工智能基础_机器学习040_Sigmoid函数详解_单位阶跃函数与对数几率函数_伯努利分布---人工智能工作笔记0080

然后我们再来详细说一下Sigmoid函数,上面的函数的公式 我们要知道这里的,Sigmoid函数的意义,这逻辑斯蒂回归的意义就是,在多元线性回归的基础上,把 多元线性回归的结果,缩放到0到1之间对吧,根据中间的0.5为分类,小于0.5的一类,大于的一类, 这里的h theta(x) 就是概率函数 然…...

Scala---迭代器模式+Trait特质特性

Scala迭代器模式处理数据 scala中创建集合需要内存&#xff0c;集合与集合之间的转换时&#xff0c;每次转换生成新的集合时&#xff0c;新的集合也需要内存。如果有一个非常大的初始集合&#xff0c;需要经过多次转换&#xff0c;每次转换都生成一个新的集合&#xff0c;才能…...

labview运行速度太慢

找到labview程序运行速度的瓶颈 - 百度文库 LabVIEW执行速度 - 北京瀚文网星科技有限公司 性能和内存信息窗口 必需&#xff1a;基础版开发系统 选择工具性能分析性能和内存&#xff0c;可显示该窗口。 该窗口用于采集和显示VI的执行时间和内存使用信息。如在不属于项目的…...

QT基础入门【QSS】继承、命名空间中的小部件、QObject 属性介绍

继承 在经典 CSS 中,当项目的字体和颜色没有显式设置时,它会自动从父级继承。但是在使用 Qt 样式表时,默认情况下,部件不会从其父部件自动继承其字体和颜色设置。 例如,考虑一个 QPushButton 在 QGroupBox 内部: qApp->setStyleSheet("QGroupBox { color: red…...

Ubuntu18.04安装IgH主站

EtherCAT主站是EtherCAT网络中的中央控制单元,负责协调和管理连接到网络的所有从站设备。EtherCAT(Ethernet for Control Automation Technology)是一种高性能、实时的工业以太网通信协议,广泛应用于自动化和控制领域。 一、安装依赖包 sudo apt install autoconf automa…...

HTML5-原生History

更多内容&#xff0c;访问: history hash 单页面应用和多页面应用 React-Router源码分析-History库 History库源码分析-Action 动作类型 History库源码分析-createLocation History库源码分析-createPath History库源码分析-parsePath history 浏览器历史记录对象 属性: le…...

无需公网IP,使用MCSM面板一键搭建我的世界Minecraft服务器联机游戏

文章目录 前言1.Mcsmanager安装2.创建Minecraft服务器3.本地测试联机4. 内网穿透4.1 安装cpolar内网穿透4.2 创建隧道映射内网端口 5.远程联机测试6. 配置固定远程联机端口地址6.1 保留一个固定TCP地址6.2 配置固定TCP地址 7. 使用固定公网地址远程联机 前言 MCSManager是一个…...

高斯积分-Gaussian Quadrature

https://mathworld.wolfram.com/GaussianQuadrature.html...

Linux下非root用户安装CUDA

目录 前言 参考链接 步骤 一. 首先&#xff0c;需要查看系统版本&#xff1a; 二. 安装包下载。 下载CUDA&#xff1a; cuDNN下载 三. 开始安装CUDA和cuDNN 安装CUDA 修改环境变量 安装 cuDNN 查看是否安装成功&#xff0c;输入nvcc -V 前言 由于一些代码实现&…...

【bugfix】安装 flash-attn 报错

目录 1. 报错信息 2. 解决方法 安装 flash attention 报错 1. 报错信息 Building wheel for flash-attn (setup.py) ... error error: subprocess-exited-with-error 或者 Building wheel for flash-attn (pyproject.toml) did not run successfully 甚至更多问题。 2. 解…...

技术实践|高斯集群服务器双缺省网关故障分析

导语&#xff1a;当前国产化数据库使用范围越来越广泛&#xff0c;在GaussDB数据库的使用过程中难免会遇到一些问题&#xff0c;有的问题是由于在安装过程中没有注意细节而产生的&#xff0c;多数隐患问题都是在特定场景下才会暴露出来&#xff0c;且暴露的时间未知&#xff0c…...

手把手教你搭建Maven私服

Java全能学习面试指南&#xff1a;https://javaxiaobear.cn 1. Maven私服简介 ①私服简介 Maven 私服是一种特殊的Maven远程仓库&#xff0c;它是架设在局域网内的仓库服务&#xff0c;用来代理位于外部的远程仓库&#xff08;中央仓库、其他远程公共仓库&#xff09;。 当然…...

LeetCode 面试题 16.25. LRU 缓存

文章目录 一、题目二、C# 题解 一、题目 设计和构建一个“最近最少使用”缓存&#xff0c;该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)&#xff0c;并在初始化时指定最大容量。当缓存被填满时&#xff0c;它应该删除最近最少使用的…...

LaTeX 数学公式常见问题及解决方案

本文汇总了博主在使用 LaTeX 写文档过程中遇到的所有数学公式常见问题及对应的 LaTeX 解决方案 持续更新... 目录 1. 连等式2. 公式重新开始编号2.1 图片/表格重新编号 1. 连等式 在数学公式推导过程中常常会遇到如 Figure 1 所示的连等式&#xff0c;一般需要保证等号或者不等…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...