当前位置: 首页 > 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;一般需要保证等号或者不等…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...