堆与滑动窗口的结合(算法村第十六关黄金挑战)
滑动窗口最大值
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], k = 1
输出:[1]
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
堆与滑动窗口
参考题解:239. 滑动窗口最大值 - 力扣(LeetCode)
public int[] maxSlidingWindow(int[] nums, int k)
{//创建一个大根堆,节点由nums中元素的值pair[0]及其下标pair[1]组成PriorityQueue<int[]> maxHeap = new PriorityQueue<>((int[] pair1, int[] pair2) -> (pair2[0] - pair1[0]));//将前k个元素加入大根堆for (int i = 0; i < k; i++)maxHeap.offer(new int[]{nums[i], i});//答案数组,存滑动窗口中的最大值int[] ans = new int[nums.length - k + 1];//存滑动窗口的第一个最大值ans[0] = maxHeap.peek()[0];//滑动窗口开始移动for (int i = k; i < nums.length; i++){maxHeap.offer(new int[]{nums[i], i});//不断移除堆顶最大值,直到堆顶元素的索引出现在滑动窗口中//i - k是滑动窗口(闭区间)的左边界while (maxHeap.peek()[1] <= i - k)maxHeap.poll();//滑动窗口移动后,从ans[1]开始存ans[i - k + 1] = maxHeap.peek()[0];}return ans;
}
相关文章:
堆与滑动窗口的结合(算法村第十六关黄金挑战)
滑动窗口最大值 239. 滑动窗口最大值 - 力扣(LeetCode) 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大…...

ES6-let
一、基本语法 ES6 中的 let 关键字用于声明变量,并且具有块级作用域。 - 语法:let 标识符;let 标识符初始值; - 规则:1.不能重复声明let不允许在相同作用域内重复声明同一个变量2.不存在变量提升在同一作用域内,必须先声明才能试…...

如何发布自己的npm包:
1.创建一个打包组件或者库: 安装weback: 打开项目: 创建webpack.config.js,创建src目录 打包好了后发现两个js文件都被压缩了,我们想开发使用未压缩,生产使用压缩文件。 erserPlugin:(推荐使用…...

JavaSE——流程控制-跳转关键字(break、continue),小案例(随机数、猜数字)
目录 跳转关键字 小案例(随机数) Random 猜数字 跳转关键字 break:跳出并结束当前所在循环的执行。continue:用于跳出当前循环的当次执行,直接进入循环的下一次执行。 注意事项: break:只能…...

Java HashSet 重写 equals() 和 hashCode() 对象去重
Ailt Insert 选择 equals() 和 hashCode() package com.zhong.collection.set;import java.util.HashSet; import java.util.Objects;public class HashSetDeduplication {public static void main(String[] args) {// HashSet 对象去重HashSet<Student> students new …...

Mac电脑到手后的配置
一、Homebrew 1、Homebrew安装 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 桌面的Old_Homebrew文件夹,没有你需要的可以删除。 2、Homebrew卸载 /bin/zsh -c "$(curl -fsSL https://gitee.com/c…...

Python中的while循环,知其然知其所以然
文章目录 while循环结构1.用循环打印1 ~ 100步骤解析2. 1 ~ 100的累加和3.死循环1. 用死循环的方法实现 1 ~ 100累加和 4. 单向循环(1)打印 一行十个小星星*(2)通过打印一个变量的形式,展现一行十个小星星(3)一行十个换色的星星 ★☆★☆★☆★☆★☆(4)用一个循环,打印十行十列…...
云瞻无代码开发:连接并集成电商平台、营销系统和CRM
无缝集成优势 云瞻信息已在电商领域取得杰出成就,其亮点在于其高效的社群运营和传统导购业务。云瞻的SAAS开放平台,一个连接和集成各种应用的工具,简化了传统的API开发流程。这赋能商家,即使没有专业的技术知识,也能够…...

LeetCode-第2469题=温度转换
1.题目描述 给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度,以 摄氏度(Celsius)为单位。 你需要将摄氏度转换为 开氏度(Kelvin)和 华氏度(Fahrenheit),并以数组 ans …...

docer compose部署simple-docker
简介 一个看似简陋但是功能足够用的docker管理工具 安装 创建目录 mkdir -p /opt/simple-docker cd /opt/simple-docker 创建并启动容器 编写docker-compose.yml文件,内容如下 version: 3 services: redis: image: redis:latest restart: always web: image: registry.cn-…...

Android Studio中打开文件管理器
文章目录 一、前言二、操作步骤 一、前言 在Android Studio中有时候需要查看手机的文件目录或者复制文件,但是有时候文件管理器找不到在哪,这里记录该操作流程 二、操作步骤 第一步: 第二步: 第三步:...

算法42:天际线问题(力扣218题)---线段树
218. 天际线问题 城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息由数组 buildings 表示,其中三元组 buildings[i] [lefti, righti, heig…...

SpringBoot中使用Spring自带线程池ThreadPoolTaskExecutor与Java8CompletableFuture实现异步任务示例
场景 关于线程池的使用: Java中ExecutorService线程池的使用(Runnable和Callable多线程实现): Java中ExecutorService线程池的使用(Runnable和Callable多线程实现)_executorservice executorservice executors.newfix-CSDN博客 Java中创建线程的方式…...

OpenCV/C++:点线面相关计算(二)
接续,继续更新 OpenCV/C:点线面相关计算_线面相交的点 代码计算-CSDN博客文章浏览阅读1.6k次,点赞2次,收藏12次。OpenCV处理点线面的常用操作_线面相交的点 代码计算https://blog.csdn.net/cd_yourheart/article/details/125626239 目录 1、…...

2024最新版鸿蒙HarmonyOS开发工具安装使用指南
2024最新版鸿蒙HarmonyOS开发工具安装使用指南 By JacksonML 0. 什么是鸿蒙Harmony OS? 华为鸿蒙系统(HUAWEI Harmony OS),是华为公司在2019年8月9日于东莞举行的华为开发者大会(HDC.2019)上正式发布的分…...
Spring事务源码解析
Spring的事务属于逻辑事务。不是物理事务。 Spring并不直接管理事务,而是提供了多种事务管理器,它们将事务管理的职责委托给JDBC或者JTA等持久化机制所提供的相关平台框架的事务来实现。例如JDBC的事物管理器就是DataSourceTransactionManager。 Spr…...
71.Spring和SpringMVC为什么需要父子容器?
71.Spring和SpringMVC为什么需要父子容器? 就功能性来说不用子父容器也可以完成(参考:SpringBoot就没用子父容器) 1、所以父子容器的主要作用应该是划分框架边界。有点单一职责的味道。service、dao层我们一般使用spring框架 来…...

标准库 STM32+EC11编码器+I2C ssd1306多级菜单例程
标准库 STM32EC11编码器I2C ssd1306多级菜单例程 📌原创项目来源于:https://github.com/AdamLoong/Embedded_Menu_Simple📍相关功能演示观看:https://space.bilibili.com/74495335 单片机多级菜单v1.2 👉本次采用的是原…...

通过 ChatGPT 的 Function Call 查询数据库
用 Function Calling 的方式实现手机流量包智能客服的例子。 def get_sql_completion(messages, model"gpt-3.5-turbo"):response client.chat.completions.create(modelmodel,messagesmessages,temperature0,tools[{ # 摘自 OpenAI 官方示例 https://github.com/…...

LLM(大语言模型)——大模型简介
目录 概述 发展历程 大语言模型的概念 LLM的应用和影响 大模型的能力、特点 大模型的能力 涌现能力(energent abilities) 作为基座模型支持多元应用的能力 支持对话作为统一入口的能力 大模型的特点 常见大模型 闭源LLM(未公开源…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...