剑指 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
解析：
要实现三种操作的时间复杂度为O(1),往往得采用空间换时间的思想，也就是说应该需要一个辅助的数据结构
Push_back和Pop_front采用普通队列的时候，都是O(1)时间复杂度，关键在于Max_value
Max_value暴力的话，直接遍历，O(N)
如果每次入队时都更新最大值的话，当这个最大值出队之后，就不知道队列里下一个最大值是谁了，这个方法会造成信息的丢失
那我们可以采用一个辅助队列来记录最大值，这样最大值x出队后，辅助队列头部如果也是x，那么x出辅助队列，如果辅助队列头部，不是x，则辅助队列的x不用出栈
当入栈的时候，如果辅助队列的队尾元素小于入栈值y，那么辅助队列队尾元素出栈，直到队尾元素大于等于y，为什么入队的时候需要这样操作？
因为辅助队列队尾小于y的那些元素，都是先于y入主队列的，不影响最大这个特性，只有这些小于y的元素出主队列之后，y才会出主队列，因为这些元素在主队列中排在y的前面！所以辅助队列中这些小于y的元素可以从队尾出队列，不会影响最这个特性
时间复杂度：O(1)
空间复杂度：O(N)
type MaxQueue struct {
queque []int
dqueue []int
}
func Constructor() MaxQueue {
return MaxQueue{
queque: []int{},
dqueue: []int{},
}
}
func (this *MaxQueue) Max_value() int {
if len(this.dqueue)!=0{
return this.dqueue[0]
}
return -1
}
func (this *MaxQueue) Push_back(value int) {
this.queque=append(this.queque,value)
n:=len(this.dqueue)
for i:=n-1;i>=0;i--{
if this.dqueue[i]<value{
this.dqueue=this.dqueue[0:i]
}else {
break
}
}
this.dqueue=append(this.dqueue,value)
}
func (this *MaxQueue) Pop_front() int {
if len(this.queque)==0{
return -1
}
value:=this.queque[0]
this.queque=this.queque[1:]
if value==this.dqueue[0]{
this.dqueue=this.dqueue[1:]
}
return value
}