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

239.滑动窗口最大值

leetcode原题链接

题目描述:

给你一个整数数组 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例2

输入:nums = [1,3,0,2,4]
输出:0
解释:
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k,即 0。

提示

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

解题思路:

方法一:单调队列

单调队列:队列中的元素是单调递增或单调递减的队列就是单调队列。


  1. 维护队列中的元素递增

对于这道题需要维护一个单调递增的队列。
在这里插入图片描述

由队尾到队头 元素是单调递增的。如果要入队元素大于队尾元素,则队尾元素出队,这是个循环操作,如下:

while(deque.peekLast() < newElement){deque.pollLast();
}
deque.push(newElement); // 新元素入队

  1. 如何保证队列中的元素是窗口内的,因为窗口一直在向右移动?

在这里插入图片描述

初始时,窗口为1,队列中元素为9, 8, 7。窗口向右移动时(窗口2)发现9已不是窗口中的元素,但9依然在队列中,且9为队列的队头元素,需要将9从队列的队头弹出。所以需要进行如下判断:

if(deque.peekFirst() == v){ // v为上一个窗口最左边的值。deque.poolFirst();
}

整体代码如下:

public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] ans = new int[n - k + 1];Deque<Integer> deque = new LinkedList<>();int idx = 0;for(int i = 0; i < nums.length; i++){// 保证队列中的元素是窗口内的if(!deque.isEmpty() && i - k>= 0 && nums[i - k] == deque.peekFirst()){deque.pollFirst();}// 维护队列中的元素是递增的while (!deque.isEmpty() && nums[i] > deque.peekLast()){deque.pollLast();}deque.addLast(nums[i]);if(i>= k - 1){ans[idx++] = deque.peekFirst();}}return ans;
}

方法二:线段树

百度百科:线段树


[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fEboTtnz-1690452411315)(D:\ProgramFiles\Typora\typora-images\image-20230727175053720.png)]

线段树中的每个节点存储的是这个区间的最大值。

整体代码如下:

public int[] maxSlidingWindow(int[] nums, int k) {int len = nums.length;int[] ans = new int[len - k + 1];this.tr = new Node[len * 4+1];build(1,1,len);for(int i = 0; i<len;i++){update(1,i+1,nums[i]);}for(int i = 0; i< len -k+1;i++){ans[i] = query(1,i+1,i+k);}return ans;
}class Node {int l, r, v;Node(int l, int r) {this.l = l;this.r = r;v = Integer.MIN_VALUE;}
}Node[] tr;void pushup(int u) {tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
}void build(int u, int l, int r) {tr[u] = new Node(l, r);if (l != r) {int mid = tr[u].l+tr[u].r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);}
}void update(int u, int x, int v){if(x== tr[u].l&&tr[u].r==x){tr[u].v = Math.max(tr[u].v, v);} else{int mid = tr[u].l+tr[u].r>>1;if(x<=mid){update(u<<1,x,v);} else{update(u<<1|1,x,v);}pushup(u);}
}
int query(int u, int l, int r){if(l<= tr[u].l&&tr[u].r<=r){return tr[u].v;} else{int mid = tr[u].l+tr[u].r>>1;int ans = Integer.MIN_VALUE;if(l<=mid){ans =query(u<<1,l,r);} if(r>mid){ans = Math.max(query(u<<1|1,l,r),ans);}return ans;}
}

相关文章:

239.滑动窗口最大值

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

Redis基础原理

1 概念 1.1 关系型数据库与非关系型数据库对比 关系型数据库Mysql、Oralce特点数据之间有关联&#xff1b;数据存储在硬盘上效率操作关系型数据库非常耗时 非关系型数据库redis、hbase存储key:value特点数据之间没有关联关系&#xff1b;数据存储在内存中缓存思想从缓存中获…...

.NET 5 Web API 中JWT详细教程:保护你的Web应用

第一部分&#xff1a; 理解JWT JSON Web Token&#xff08;JWT&#xff09;是一种在不同系统之间传递信息的安全方式。它由三部分组成&#xff1a;头部&#xff08;Header&#xff09;、载荷&#xff08;Payload&#xff09;和签名&#xff08;Signature&#xff09;。头部包…...

MyBatis-Plus自动填充

文章目录 一、前言二、MyBatis-Plus自动填充功能实现2.1、实体类上增加注解2.2、自定义填充类编写 一、前言 我们在建表的时候&#xff0c;所有的表都会有create_id&#xff08;创建人id&#xff09;、create_time&#xff08;创建时间&#xff09;、update_id&#xff08;更新…...

Dubbo服务提供者失效踢出原理解析

Dubbo服务提供者失效踢出原理解析 在分布式系统中&#xff0c;服务提供者的失效是一个常见而且重要的问题。Dubbo作为一款优秀的分布式服务框架&#xff0c;提供了失效踢出机制来及时剔除不可用的服务提供者&#xff0c;确保系统的稳定性和可用性。本文将深入探讨Dubbo服务提供…...

el-select下拉框处理分页数据,触底加载更多

1、声明自定义指令&#xff1a; directives: {loadmore: {inserted(el, binding) {const SELECTWRAP_DOM el.querySelector(.el-select-dropdown .el-select-dropdown__wrap);SELECTWRAP_DOM.addEventListener(scroll, function() {const condition this.scrollHeight - thi…...

如何设计自动化测试脚本?一文5个步骤带你从0到1设计

企业中如何设计自动化测试脚本呢&#xff1f;今天我们就来为大家分享一些干货。 一、线性设计 线性脚本设计方式是以脚本的方式体现测试用例&#xff0c;是一种非结构化的编码方式&#xff0c;多数采用录制回放的方式&#xff0c;测试工程师通过录制回访的访问对被测系统进行自…...

PostgreSQL实战-数据库迁移部署

PostgreSQL实战-数据库迁移部署 介绍 根据项目需求&#xff0c;我们需要将现有的PostgreSQL数据库重新部署到新的服务器上。由于项目本身就是基于PostgreSQL数据库构建的&#xff0c;因此数据库迁移将变得十分便捷。接下来&#xff0c;我将简要介绍我们的迁移步骤。 迁移步骤…...

PHP数据库

PHP MySQL 连接数据库 MySQL 简介MySQL Create 免费的 MySQL 数据库通常是通过 PHP 来使用的。 连接到一个 MySQL 数据库 在您能够访问并处理数据库中的数据之前&#xff0c;您必须创建到达数据库的连接。 在 PHP 中&#xff0c;这个任务通过 mysql_connect() 函数完成。 …...

Mybatis的基本操作--增删改查

目录 查看数据 无参数 一个参数 多个参数 添加数据 修改数据 删除数据 注释的方式进行查找数据 查看数据 分三种情况&#xff1a;无参&#xff0c;有一个参数&#xff0c;有多个参数的情况。 &#xff08;这里的详细操作步骤是博主的上一篇博客写的&#xff1a;初识My…...

Qt简单实现密码器控件

本文实例为大家分享了Qt自定义一个密码器控件的简单实现代码&#xff0c;供大家参考&#xff0c;具体内容如下 实现构思&#xff1a; 密码器的功能可以看成是计算器和登陆界面的组合&#xff0c;所以在实现功能的过程中借鉴了大神的计算器的实现代码和登陆界面实现的代码。 …...

fpga_pwm呼吸灯(EP4CE6F17C8)

文章目录 一、呼吸灯二、代码实现三、引脚分配 一、呼吸灯 呼吸灯是指灯光在微电脑的控制之下完成由亮到暗的逐渐变化&#xff0c;使用开发板上的四个led灯实现1s间隔的呼吸灯。 二、代码实现 c module pwm_led( input clk ,input rst_n ,output reg [3:0] led ); …...

WPF实战学习笔记20-设置首页启动页

文章目录 设置首页启动页增加配置接口添加接口文件&#xff1a;实现接口 配置启动选项 设置首页启动页 增加配置接口 添加接口文件&#xff1a; Mytodo.Common/IConfigureInterface.cs using System; using System.Collections.Generic; using System.Linq; using System.T…...

uniapp实现预约时间选择弹窗组件

做了个组件&#xff0c;实现出当日预约时间组件&#xff0c;效果图如下 废话不多说&#xff0c;直接上代码&#xff0c;代码简单&#xff0c;参数自己任意改 <template><view class"inventory"><u-popup :show"show" :round"10"…...

opencv 之 外接多边形(矩形、圆、三角形、椭圆、多边形)使用详解

opencv 之 外接多边形&#xff08;矩形、圆、三角形、椭圆、多边形&#xff09;使用详解 本文主要讲述opencv中的外接多边形的使用&#xff1a; 多边形近似外接矩形、最小外接矩形最小外接圆外接三角形椭圆拟合凸包 将重点讲述最小外接矩形的使用 1. API介绍 #多边形近似 v…...

断路器分合闸速断试验

试验目的 高压断路器的分、 合闸速度是断路器的重要特性参数, 反映出断路器的操动机构 与传动机构在分、 合闸过程中的运动特征。 断路器分、 合闸速度超出或者低于规定值 均会影响断路器的运行状态和使用寿命。 断路器合闸速度不足, 将会引起触头合闸振 颤, 预击穿时间过长。…...

【Redis】如何实现一个合格的分布式锁

文章目录 参考1、概述2、Redis粗糙实现3、遗留问题3.1、误删情况3.2、原子性保证3.3、超时自动解决3.4、总结 4、Redis实现优缺5、集群问题5.1、主从集群5.2、集群脑裂 6、RedLock7、Redisson7.1、简单实现7.2、看门狗机制 参考 Redisson实现Redis分布式锁的N种姿势 (qq.com)小…...

组件化开发复习

1.vue的根组件使用 // 1.创建appconst app Vue.createApp({// data: option apidata() {return {message: "Hello Vue",counter: 0,counter2: 0,content: ""}},watch: {content(newValue) {console.log("content:", newValue)}}}) createApp 函…...

【设计模式】设计原则-里氏替换原则

里氏替换原则 定义 任何基类可以出现的地方&#xff0c;子类一定可以出现。 通俗理解&#xff1a;子类可以扩展父类的功能&#xff0c;但不能改变父类原有的功能。 换句话说&#xff0c;子类继承父类时&#xff0c;除添加新的方法完成新增功能外&#xff0c;尽量不要重写父类…...

v2ex站点base64编码解码

最近在刷v站&#xff0c;我毕竟也是入坑不久的小白&#xff0c;发现各位兄弟的联系方式都是乱码&#xff0c;我以为是经过md5处理之类的&#xff0c;最后搜了下发现是对信息进行了base64编解码处理&#xff0c;目的是为了防止社工对个人信息的爬取处理。 下面是通过python对个人…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...