【Golang】LeetCode-剑指Offer-面试题59 - II-队列的最大值

题目

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof

解题思路

• 双队列
  • 入队
    • q1 : 单向队列，用于存储进队的值
    • max ：双向队列，较大值进队，较小值出队，用于存储最大值，呈递减序列
  • 出队
    • q1 : 首部出队
    • max：队列的首部与 q1 出队的值作比较，如果相同，那么一起出队
  • 若队列为空，pop_front 和 max_value 返回 -1

代码

–执行用时：88 ms --内存消耗：7.8 MB

type MaxQueue struct {
    q1 []int
    max []int
}

func Constructor() MaxQueue {
    return MaxQueue{
        make([]int,0),
        make([]int,0),
    }
}

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.q1 = append(this.q1,value)
    for len(this.max) != 0 && value > this.max[len(this.max)-1]{
        this.max = this.max[:len(this.max)-1]
    }
    this.max = append(this.max,value)
}

func (this *MaxQueue) Pop_front() int {
    n := -1
    if len(this.q1) != 0{
        n = this.q1[0]
        this.q1 = this.q1[1:]
        if this.max[0] == n{
            this.max = this.max[1:]
        }
    }
    return n
}

/**
 * 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();
 */
           

在LeetCode该题中，我也有提交题解，欢迎查看。昵称:Sakura。