golang刷leetcode 技巧（15）队列的最大值

golang算法架构leetcode技术php 2020-02-20

293

请定义一个队列并实现函数 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 max函数

文章转载自golang算法架构leetcode技术php，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

golang刷leetcode 技巧（15）队列的最大值

评论