面试题59 - II. 队列的最大值

[yankewei]

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

解答

先来理解题意，就是想要一个队列，这个队列具体怎么实现我不管，但是我需要通过max_value, push_back,pop_front这三个接口来满足我的需要：
max_value: 获取当前队列最大值
push_back: 把元素追加到末尾
pop_front: 弹出第一个元素
这三个接口的时间复杂度需要是O(1)
刚开始我以为直接一个切片，外加一个最大值就可以了，但是没有想到这个最大值是一只变化的，因为我在pop_front的时候可能把最大值弹出了，这时需要保留下一个最大值。下一个最大值就联想到了单调栈。
这里有一点很重要，因为我们弹出的队列的第一个元素，所以如果后边的值大于第一个元素，即使弹出也不影响我们的最大值，基于这个，我们可以实现一个单调递减的栈

type MaxQueue struct {
    List []int
    MaxValue []int
}

func Constructor() MaxQueue {
    return MaxQueue{List: []int{}, MaxValue: []int{}}
}


func (this *MaxQueue) Max_value() int {
    if len(this.MaxValue) == 0 {
        return -1
    }
    return this.MaxValue[0]
}


func (this *MaxQueue) Push_back(value int)  {
    for len(this.MaxValue) != 0 && value > this.MaxValue[len(this.MaxValue) - 1] {
        this.MaxValue = this.MaxValue[:len(this.MaxValue)-1]
    }
    this.MaxValue = append(this.MaxValue, value)
    this.List = append(this.List, value)
}


func (this *MaxQueue) Pop_front() int {
    if len(this.List) == 0 {
        return -1
    }
    popNum := this.List[0]
    if popNum == this.MaxValue[0] {
        this.MaxValue = this.MaxValue[1:len(this.MaxValue)]
    }
    this.List = this.List[1:len(this.List)]
    return popNum
}

其实也有点类似，一个随时进行的滑动窗口如何寻找窗口中的最大值。遇到这种类型的题也可以使用这个方法