数据结构学习 jz59 滑动窗口的最大值

2024-01-15 23:36

本文主要是介绍数据结构学习 jz59 滑动窗口的最大值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

关键词:排序 大顶堆 双端队列

题目: 望远镜中最高的海拔

方法一:维护一个辅助队列。

方法二:大顶堆。

我还在主站 239 写了找最小值的方法。

方法一:最优解

这个方法和jz30维护一个非严格递减的辅助栈是基本一样的。

思路:

看了k神答案才懵懵懂懂会。建议看。

维护一个limit大小的双端队列作为辅助,这个双端队列存的是有可能成为最大值的潜在选手,如果在这个窗口内,后面的数大过了一些潜在选手,那么就把这些不够大的潜在选手淘汰(pop)。

我们需要一直保持这个双端的队列的非严格递减性。

可以将 “未形成窗口” 和 “形成窗口后” 两个阶段拆分到两个循环里实现。

复杂度计算:

时间复杂度O(n)

空间复杂度O(limit)

代码:

class Solution {
public:vector<int> maxAltitude(vector<int>& heights, int limit) {vector<int> result;if(heights.empty()||limit==0) return result;deque<int> dq;//双端非严格递减队列dq.push_back(heights[0]);//初始化第一个数//未形成窗口for(int i=1;i<limit;++i){while(!dq.empty()&&heights[i]>dq.back()) {dq.pop_back();}dq.push_back(heights[i]);}result.push_back(dq[0]);//形成窗口for(int i=limit;i<heights.size();++i){//出栈最大值if(heights[i-limit]==dq[0]){dq.pop_front();}while(!dq.empty()&&heights[i]>dq.back()){dq.pop_back();}dq.push_back(heights[i]);result.push_back(dq[0]);}return result;}
};

方法二:

 大顶堆,优先序列。记录pair(val,index),top的index如果超过了窗口左端,就推出。

思路:

这个方法很好理解,我刚开始也是希望用大顶堆做,但是没想到怎么删除已经超过窗口的数,这里给了我启发,只要记录一个pair(val,index),就可以了。

在查询最大值的时候,同时检查index,如果超过了窗口的左端,那么就直接pop,直到找到窗口内的最大值。

复杂度计算:

时间复杂度O(nlogn)

空间复杂度O(n)

代码:

class Solution {
public:vector<int> maxAltitude(vector<int>& heights, int limit) {vector<int> result;if(heights.empty()||limit==0) return result;priority_queue<pair<int,int>> q;//未形成窗口前for(int i=0;i<limit;++i){q.push({heights[i],i});}result.push_back(q.top().first);//形成窗口后for(int i=limit;i<heights.size();++i){q.push({heights[i],i});while(q.top().second<=i-limit){q.pop();}result.push_back(q.top().first);}return result;}
};

这篇关于数据结构学习 jz59 滑动窗口的最大值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610564

相关文章

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

bat脚本启动git bash窗口,并执行命令方式

《bat脚本启动gitbash窗口,并执行命令方式》本文介绍了如何在Windows服务器上使用cmd启动jar包时出现乱码的问题,并提供了解决方法——使用GitBash窗口启动并设置编码,通过编写s... 目录一、简介二、使用说明2.1 start.BAT脚本2.2 参数说明2.3 效果总结一、简介某些情

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法,它将时间划分为若干个固定大小的窗口,每个窗口内记录了该时间

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;