您好,登录后才能下订单哦!
这篇文章主要介绍了golang刷leetcode技巧之如何实现队列的最大值,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。
若队列为空,pop_front 和 max_value 需要返回 -1
示例 1:
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2:
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
限制:
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
解题思路:
1,对于先进先出,O(1),显然是一个基本的队列可以搞定
2,但是实现O(1)的max,需要优先队列
3,但是本题的技巧在于:优先队列只需要按照插入顺序,保留前几个
4,具体原因:
A,如果插入元素比现在优先队列元素都小,插入队尾即可,这很好理解
B,如果插入元素A比现在优先队列某些元素a,b,c大,那么,a,b,c 出队的时候,最大元素肯定大于等于A,所以,没有必要维护a,b,c的优先队列了
代码实现
type MaxQueue struct {
queue []int
max []int
}
func Constructor() MaxQueue {
return MaxQueue{}
}
func (this *MaxQueue) Max_value() int {
if len(this.max)==0{
return -1
}
return this.max[0]
}
func (this *MaxQueue) Push_back(value int) {
this.queue=append(this.queue,value)
i:=0
for ;i<len(this.max);i++{
if this.max[i]<=value{
break
}
}
this.max=append(this.max[:i],value)
}
func (this *MaxQueue) Pop_front() int {
if len(this.queue)==0{
return -1
}
v:=this.queue[0]
this.queue=this.queue[1:]
if v==this.max[0]{
this.max=this.max[1:]
}
return v
}
/**
* Your MaxQueue object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Max_value();
* obj.Push_back(value);
* param_3 := obj.Pop_front();
*/
感谢你能够认真阅读完这篇文章,希望小编分享的“golang刷leetcode技巧之如何实现队列的最大值”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。