【golang必备算法】单调队列 Letecode 239. 滑动窗口最大值
2021/11/3 17:10:06
本文主要是介绍【golang必备算法】单调队列 Letecode 239. 滑动窗口最大值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
单调队列
今天刷力扣,碰到一道关于单调队列的题,总结一下
239. 滑动窗口最大值
单调队列思想:
队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。
单调队列不是单纯的给队列中元素排序,那和优先级队列没有什么区别了。
设计时要注意的:
- pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
- push(value):如果push的元素value大于入口元素的数值,那么就将队列出口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
type MyQueue struct{ //创建结构体 queue []int } func NewMyQueue() *MyQueue { //初始化函数 return &MyQueue{ queue: make([]int, 0), } } func (m *MyQueue) Push(k int){ //将单调队列中比k小的全都弹出 if len(m.queue)>0 && k>m.queue[0]{ //队列中所有的元素都比k小 m.queue=[]int{} } for len(m.queue)>0 && m.queue[len(m.queue)-1]<k{ // 队列中所可能存在元素比k小 m.queue=m.queue[:len(m.queue)-1] } m.queue=append(m.queue,k) } func (m *MyQueue) Pop(t int){ if m.queue[0]==t{ //判断滑动窗口最左边元素t是不是单调队列最大值,若是弹出,否则什么都不用做 m.queue=m.queue[1:] } } func maxSlidingWindow(nums []int, k int) []int { queue:=NewMyQueue() arr:=make([]int,0) left,right:=0,k-1 for i:=left;i<=right;i++{ queue.Push(nums[i]) } arr=append(arr,queue.queue[0]) right++ for right<=len(nums)-1{ queue.Pop(nums[left]) queue.Push(nums[right]) arr=append(arr,queue.queue[0]) left++ right++ } return arr }
这篇关于【golang必备算法】单调队列 Letecode 239. 滑动窗口最大值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-03如何用Google Gemini和MyScaleDB打造一个基于检索增强生成技术的聊天机器人
- 2024-12-24MongoDB资料:新手入门完全指南
- 2024-12-20go-zero 框架的 RPC 服务 启动start和停止 底层是怎么实现的?-icode9专业技术文章分享
- 2024-12-19Go-Zero 框架的 RPC 服务启动和停止的基本机制和过程是怎么实现的?-icode9专业技术文章分享
- 2024-12-18怎么在golang中使用gRPC测试mock数据?-icode9专业技术文章分享
- 2024-12-15掌握PageRank算法核心!你离Google优化高手只差一步!
- 2024-12-15GORM 中的标签 gorm:"index"是什么?-icode9专业技术文章分享
- 2024-12-11怎么在 Go 语言中获取 Open vSwitch (OVS) 的桥接信息(Bridge)?-icode9专业技术文章分享
- 2024-12-11怎么用Go 语言的库来与 Open vSwitch 进行交互?-icode9专业技术文章分享
- 2024-12-11怎么在 go-zero 项目中发送阿里云短信?-icode9专业技术文章分享