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

算法通关村第十六关-黄金挑战滑动窗口与堆的结合

大家好我是苏麟 , 今天带来一道小题 .

滑动窗口最大值

描述 :

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

返回 滑动窗口中的最大值 

题目 :

LeetCode 239.滑动窗口最大值 :

239. 滑动窗口最大值

分析 :

这种方法我们在基础算法的堆部分介绍过。对于最大值、K个最大这种场景,优先队列(堆)是首先应该考虑的思路。大根堆可以帮助我们实时维护一系列元素中的最大值。


本题初始时,我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组(numindex),表示元素num 在数组中的下标为index。

解析 :

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){public int compare(int[] a,int[] b){return a[0] != b[0] ? b[0] - a[0] : b[1] - a[1];}});for(int i = 0;i< k; i++){pq.offer(new int[]{nums[i],i});}int[] arr = new int[n - k + 1];arr[0] = pq.peek()[0];for(int i= k;i < n;i++){pq.offer(new int[]{nums[i],i});while(pq.peek()[1] <= i - k){pq.poll();}arr[i - k + 1] = pq.peek()[0];}return arr;}
}

这期就到这里 , 下期见!

相关文章:

算法通关村第十六关-黄金挑战滑动窗口与堆的结合

大家好我是苏麟 , 今天带来一道小题 . 滑动窗口最大值 描述 : 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 题目 : …...

基于jsp的搜索引擎

摘 要 随着互联网的不断发展和日益普及&#xff0c;网上的信息量在迅速地增长&#xff0c;在2004年4月&#xff0c;全球Web页面的数目已经超过40亿&#xff0c;中国的网页数估计也超过了3亿。 目前人们从网上获得信息的主要工具是浏览器&#xff0c;搜索引擎在网络中占有举足轻…...

【Altium designer 20】

Altium designer 20 1. Altium designer 201.1 原理图库1.1.1 上划岗 在字母前面加\在加字母1.1.2 自定义快捷键1.1.3 对齐1.1.4 在原有的电路图中使用封装1.1.5 利用excel创建IC类元件库1.1.6 现有原理图库分类以及调用1.1.7 现有原理图库中自动生成原理图库 1.2 绘制原理图1.…...

Proteus仿真--基于1602LCD与DS18B20设计的温度报警器

本文介绍基于1602LCD与DS18B20设计的温度报警器设计&#xff08;完整仿真源文件及代码见文末链接&#xff09; 仿真图如下 其中温度传感器选用DS18B20器件&#xff0c;主要用于获取温度数据并上传&#xff0c;温度显示1602LCD液晶显示器&#xff0c;报警模块选用蜂鸣器&#…...

Clickhouse Join

ClickHouse中的Hash Join, Parallel Hash Join, Grace Hash Join https://www.cnblogs.com/abclife/p/17579883.html https://clickhouse.com/blog/clickhouse-fully-supports-joins-full-sort-partial-merge-part3 总结 本文描述并比较了ClickHouse中基于内存哈希表的3种连接…...

Arduino驱动STS35数字温度传感器(温湿度传感器)

目录 1、传感器特性 2、硬件原理图 3、控制器和传感器连线图 4、驱动程序 STS35瑞士Sensirion公司新推出的温度传感器,STS35提供了一个完全校准、线性和供电电压补偿的数字输出&...

一起学docker系列之十八Docker可视化工具 Portainer:简介与安装

目录 前言1 简介2 安装过程2.1 创建docker容器数据卷2.2 构建运行protainer容器 3 Portainer 软件详细说明与界面导览3.1 查看本地Docker情况3.2 操作功能3.3 创建容器3.4 部署容器 4 Portainer的优势结语参考地址 前言 Docker作为容器化解决方案的热门工具&#xff0c;其可视…...

【数据结构】线段树

目录 1.概述2.代码实现2.1.聚合操作——求和2.2.聚合操作——求和、求最小值、求最大值 3.应用4.与前缀和之间的区别 更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。 1.概述 &#xff08;1&#xff09;线段树 (Segment Tree) 是一种二叉树形数据结构&#xff…...

王道数据结构课后代码题p175 06.已知一棵树的层次序列及每个结点的度,编写算法构造此树的孩子-兄弟链表。(c语言代码实现)

/* 此树为 A B C D E F G 孩子-兄弟链表为 A B E C F G D */ 本题代码如下 void createtree(tree* t, char a[], int degree[], int n) {// 为B数组分配内存tree* B (tree*)malloc(sizeof(tree) * n);int i 0;i…...

filter过滤器

package com.it.filter;import javax.servlet.*; import javax.servlet.annotation.WebFilter;import java.io.IOException;WebFilter(urlPatterns"/*") public class DemoFilter implements Filter {Override // 初始化的方法 只要调用一次public void init(Filte…...

MES物料的动态批次管理漫谈

在制造企业中&#xff0c;原辅材料占产品制造总成本基本在60%以上&#xff0c;特殊材料加工企业可能达到80%以上&#xff0c;按“2/8管理原则”管理好物料就基本做好制造企业的成本管理&#xff0c;这也许是很多企业向“数字化转型”的一个主要原因&#xff0c;希望借助数字信息…...

【爬虫逆向分析实战】某笔登录算法分析——本地替换分析法

前言 作者最近在做一个收集粉币的项目&#xff0c;可以用来干嘛这里就不展开了&#x1f601;&#xff0c;需要进行登录换算token从而达到监控收集的作用&#xff0c;手机抓包发现他是通过APP进行计算之后再请求接口的&#xff0c;通过官网分析可能要比APP逆向方便多&#xff0…...

vue3使用动态component

使用场景&#xff1a; 多个组件通过component标签挂载在同一个组件中&#xff0c;通过触发时间进行动态切换。vue3与vue2用法不一样&#xff0c;这里有坑&#xff01; 使用方法&#xff1a; 1.通过vue的defineAsyncComponent实现挂载组件 2.component中的is属性 父组件&am…...

单机游戏推荐:巨击大乱斗 GIGABASH 中文安装版

在泰坦之中称霸天下吧&#xff01;《GigaBash 巨击大乱斗》是一款多人战斗擂台游戏&#xff0c;有着受特摄片启发的巨型怪兽&#xff0c;具有传奇色彩的英雄&#xff0c;震天动地的特别攻击&#xff0c;以及可以完全摧毁的擂台场景。 ​游戏特点 怪物大解放 多达10个独特的角…...

计算机系统启动过程

计算机系统启动过程 阅读笔记&#xff1a; 《计算机体系结构基础&#xff08;第三版&#xff09;》-- 胡伟武 第7章&#xff1a;计算机系统启动过程分析 系统启动的整个过程中, 计算机系统在软件的控制下由无序到有序, 所有的组成部分都由程序管理, 按照程序的执行发挥各自的功…...

DedeCms后台文章列表文档id吗?或者快速定位id编辑文章

我们在建站时有的时候发现之前的文章有错误了&#xff0c;要进行修改&#xff0c;但又不知道文章名&#xff0c;只知道大概的文章id&#xff0c;那么可以搜索到DedeCms后台文章列表文档id吗&#xff1f;或者快速定位文章id方便修改&#xff1f; 第一种方法&#xff1a;复制下面…...

【开发问题解决方法记录】03.dian

登录提示 ERR-1002 在应用程序 "304" 中未找到项 "ROLE_ID" 的项 ID。 一开始找错方向了&#xff0c;以为是代码错误&#xff0c;但是后来在蒋老师的提醒下在共享组件-应用程序项 中发现设的项不是ROLE_ID而是ROLEID&#xff0c;怪不得找不到ORZ 解决方法…...

QT之QString

QT之QString 添加容器 点击栅格布局 添加容器&#xff0c;进行栅格布局 布局总结&#xff1a;每一个模块放在一个Group中&#xff0c;排放完之后&#xff0c;进行栅格布局。多个Group进行并排时&#xff0c;先将各个模块进行栅格布局&#xff0c;然后都选中进行垂直布…...

常见的几种计算机编码格式

前言&#xff1a; 计算机编码是指将字符、数字和符号等信息转换为计算机可识别的二进制数的过程&#xff0c;正因如此&#xff0c;计算机才能识别中英文等各类字符。计算机中有多种编码格式用于表示和存储文本、字符和数据&#xff0c;实际走到最后都是二进制&#xff0c;本质一…...

3D旋转tab图

上图 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>3D旋转tab图</title><style>* {margin: 0;padding: 0;}body {height: 100vh;background: linear-gradient(to top, #29323c, #…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...