leetcode 热题 100_滑动窗口最大值

news/2024/4/13 10:57:41/文章来源:https://blog.csdn.net/lll2034006613/article/details/136513592

题解一:

        双端队列:滑动窗口的本质是在窗口末尾添加一个元素,并移除头部的一个元素。对于添加的元素,直接和当前最大值比较即可,但对于移除的元素,如果移除的是原先的最大值,则需要重新遍历窗口寻找新的最大值,因此优化的重点在于避开遍历窗口这一步骤。通过构造一个递减的Deque双端队列,我们可以将当前最大值维护在队首,并且当最大值被移除时,新的最大值依然在队首。而添加的元素则可以从队尾插入,同时,可以将队尾小于添加元素的值全部移除,因为位于窗口末尾的元素一定比其他元素晚移除,比它小的值不可能成为窗口的最大值。以下附上动画演示(来源. - 力扣(LeetCode))

import java.util.Deque;
import java.util.LinkedList;class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] maxNums = new int[nums.length - k + 1];Deque<Integer> deque = new LinkedList<>();for (int left = 1 - k, right = 0; right < nums.length; left++, right++) {if (left > 0 && deque.peekFirst() == nums[left - 1])deque.removeFirst();while (!deque.isEmpty() && deque.peekLast() < nums[right]) {deque.removeLast();}deque.addLast(nums[right]);if (left >= 0) maxNums[left] = deque.peekFirst();}return maxNums;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997715.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

甘特图资源视图和任务视图的区别

甘特图(Gantt chart)是一种常用的项目管理工具,用于直观地展示项目的进度和各项任务的时间安排。甘特图包含资源视图和任务视图两种视角。 一个项目的甘特图demo &#xff1a; https://zz-plan.com/share/87f1340286f1343ba5 资源视图主要显示项目中不同资源的分配和利用情况…

大数据Doris(六十七):Doris on ES在快手商业化的架构实现

文章目录 Doris on ES在快手商业化的架构实现 一、架构图

子查询与连表查询

子查询与连表查询 标签:数据库 子查询 mysql> explain select e.empno,e.ename,(select dname from dept d where e.deptno d.deptno) as dname from emp e where e.deptno 1; -------------------------------------------------------------------------------------…

c++ 11 新特性 不同数据类型之间转换函数之const_cast

一.不同数据类型之间转换函数const_cast介绍 const_cast是C11中引入的一种类型转换操作符&#xff0c;用于修改类型的const或volatile属性。const_cast的主要用途是移除对象的常量性&#xff0c;它是唯一具有此能力的C风格的转型操作符。在C11中&#xff0c;const_cast可以完成…

【uni-app小程序开发】实现一个背景色渐变的滑动条slider

最近做的一个用uni-app+vue2开发的微信小程序项目中要实现一个滑动进度控制条,如下图所示: 1. 滑动条需要渐变背景色 2. 滑块的背景色需要与当前位置滑动条的背景色一致(动态改变) 碰到这样的需求,我当然先是看看官方提供的slider组件和uView里的u-slider组件能不能满足…

华为OD机试 - 字符串统计(Java 2024 C卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述1、输入2、输出3、说明 四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2024C卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&a…

LeetCode每日一题[c++]-找出美丽数组的最小和

题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你两个正整数&#xff1a;n 和 target 。如果数组 nums 满足下述条件&#xff0c;则称其为 美丽数组 。 nums.length n.nums 由两两互不相同的正整数组成。在范围 [0, n-1] 内&#xff0c;不存在…

kmc密钥管理的基本功能是什么

KMC(密钥管理中心)在公钥基础设施中占据着举足轻重的地位&#xff0c;它是专门负责为CA(证书授权)系统提供一系列密钥服务的核心组件。这些服务包括但不限于密钥的生成、保存、备份、更新、恢复以及查询等&#xff0c;旨在解决分布式企业应用环境中大规模密码技术应用所带来的密…

最优算法100例之01-求数组中超过一半的数字

专栏主页:计算机专业基础知识总结(适用于期末复习考研刷题求职面试)系列文章https://blog.csdn.net/seeker1994/category_12585732.html 题目描述 组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的、都是整数,并且给定的数组总是存在…

获取C语言语句对应的汇编码和机器指令

借助IDE的调试功能 以CodeBlocks为例&#xff0c;先设置断点&#xff0c;然后点击红色三角形调试。 然后选择Debug➡ Debugging Windows➡Disassembly 就可以看到了 使用命令行 在工程文件中&#xff0c;一般可以找到一个.o文件。如果没有&#xff0c;可以先在program.c的目录下…

Android APK体积优化指南:清理项目,打造更小的APK、更快的构建速度和更好的开发体验

Android APK体积优化指南&#xff1a;清理项目&#xff0c;打造更小的APK、更快的构建速度和更好的开发体验 在任何软件项目中&#xff0c;开发是一个持续的过程&#xff0c;随着时间的推移&#xff0c;代码库会变得越来越复杂。这种复杂性可能导致构建时间变慢、APK体积变大&…

【排序算法】深入理解快速排序算法:从原理到实现

目录 1. 引言 2. 快速排序算法原理 3. 快速排序的时间复杂度分析 4. 快速排序的应用场景 5. 快速排序的优缺点分析 5.1 优点&#xff1a; 5.2 缺点&#xff1a; 6. Java、JavaScript 和 Python 实现快速排序算法 6.1 Java 实现&#xff1a; 6.2 JavaScript 实现&#…

【机器学习300问】28、什么是决策树?

〇、两个预测任务 &#xff08;1&#xff09;任务一&#xff1a;银行预测偿还能力 当前&#xff0c;某银行正致力于发掘潜在的放贷用户。他们掌握了每位用户的三个关键特征&#xff1a;房产状况、婚姻状况以及年收入。此外&#xff0c;银行还拥有过往这些用户的债务偿还能力的…

基于单片机的晾衣架控制系统设计

目 录 摘 要 I Abstract II 引 言 1 1 系统方案设计 3 1.1 系统方案论证 3 1.2 系统工作原理 4 2 硬件设计 5 2.1 单片机 5 2.2 按键设计 7 2.3 光线检测模块 8 2.4 雨滴检测模块 9 2.5 电压比较器 10 2.6 微动步进电动机 11 2.7 硬件电路原理图 12 3 系统主要软件设计 14 3.1…

Dynamo——常用几何形体的创建与编辑(一)

前面我们已经把理论知识大概梳理了一遍&#xff0c;接下来&#xff0c;我们来聊一聊 Dynamo 中关于几何形体的创建方法。 一、多边形 [Polygon.ByPoints 和 Polygon.RegularPolygon] 输入多边形的各个顶点坐标&#xff0c;并使用 “List.Create” 节点&#xff0c;将多个坐标点…

可视化您的 RAG 数据 — 使用 Ragas 评估您的检索增强生成系统

如何使用 UMAP 降维来显示多个评估问题及其与 Ragas、OpenAI、Langchain 和 ChromaDB 的源文档的关系 检索增强生成&#xff08;RAG&#xff09;在工作流中增加了一个检索步骤LLM&#xff0c;使其能够在回答问题和查询时从其他来源&#xff08;如私人文档&#xff09;查询相关数…

【漏洞复现】大华DSS数字监控系统配置系统后台弱口令漏洞

Nx01 产品简介 大华DSS数字监控系统是一个在通用安防视频监控系统基础上设计开发的系统&#xff0c;除了具有普通安防视频监控系统的实时监视、云台操作、录像回放、报警处理、设备治理等功能外&#xff0c;更注重用户使用的便利性。 Nx02 漏洞描述 大华DSS数字监控系统/confi…

Spring Boot异常处理和单元测试

1.SpringBoot异常处理 1.1.自定义错误页面 SpringBoot默认的处理异常的机制&#xff1a;SpringBoot 默认的已经提供了一套处理异常的机制。一旦程序中出现了异常 SpringBoot 会向/error 的 url 发送请求。在 springBoot 中提供了一个叫 BasicErrorController 来处理/error 请…

【随笔】程序员如何选择职业赛道,目前各个赛道的现状如何,那个赛道前景巨大

大家好&#xff0c;我是全栈小5&#xff0c;欢迎阅读文章&#xff01; 此篇是【话题达人】系列文章&#xff0c;这一次的话题是《程序员如何选择职业赛道》 目录 背景热度柱状图赛道热度C/C云原生人工智能前沿技术软件工程后端JavaJavascriptPHPPython区块链大数据移动开发嵌入…

css flex 布局换行

默认使用display: flex;是不换行的&#xff0c;只需要加上flex-wrap: wrap;就行了&#xff0c;效果图 .app-center {display: flex;flex-wrap: wrap;justify-content:flex-start; } 通过上面我们发现虽然时间换行了&#xff0c;但是每行的边距不一样 加上这个就行了&#xff…