问题
- 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
解决
//1、暴力解法，直接创建一个队列(使用数值模拟出队列效果，通过移动指针达到移除添加元素的效果)
class MaxQueue {
int[] queue=new int[10000];
int begin=0,end=0;
//队首元素不一定是最大值
public MaxQueue() { //最大队列
}
public int max_value() { //最大值
int ans=-1;
for(int i=begin;i!=end;i++){
ans=Math.max(ans,queue[i]);
}
return ans;
}
public void push_back(int value) { //入队
queue[end++]=value;
}
public int pop_front() { //出队（首）
if(begin==end) return -1;
return queue[begin++];
}
}
2、创建一个普通队列、单调队列
class MaxQueue{
Queue q;//普通队列
Deque d;//单调队列
public MaxQueue(){
q = new LinkedList();
d = new LinkedList();
}
public int max_value(){
if(q.isEmpty()){
return -1;
}
return d.peekFirst();
}
public void push_back(int value){
//当单调队列不为空，并且当前队列尾部
Original: https://www.cnblogs.com/zhangsanM/p/16614581.html
Author: new_monkey
Title: 算法：队列的最大值
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605171/
转载文章受原作者版权保护。转载请注明原作者出处！