AlgoPressAppearance
59-II-队列的最大值
题目描述
https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
请定义一个队列并实现函数 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
思路分析
创建一个默认队列储存数据，再创建一个 maxQueue 用来存放当前最大值。 举例，有数字 1,2,3,2 依次插入队列的时候，当插入 2 的时候，1就不可能是最大值了，所以我们可以从 maxQueue 里面弹出 1，同样插入3的时候，弹出前面的数字。
当插入到第四个数2的时候，因为3出列后，2有可能是最大值，所以继续插入，不弹出前面的数
注意：插入大的数之后，要从后面往前计算，删掉不符合条件的数，如 maxQueue 中已经有了 6,4,3,2 当出现5的时候，是从后面往前判断，删掉 2,3,4,直到6停止，而不是从6开始删除，因此必须是要双端队列才能满足要求。
使用 LinkedList<int> 来代替双端队列
实现代码
csharp
public class MaxQueue {
Queue<int> queue;
LinkedList<int> maxQueue;
public MaxQueue() {
queue = new Queue<int>();
maxQueue = new LinkedList<int>();
}
public int Max_value() {
int max = -1;
if(maxQueue.Count > 0){
max = maxQueue.First.Value;
}
//Console.WriteLine("max {0}", max);
return max;
}
public void Push_back(int value) {
//Console.WriteLine("push {0}", value);
queue.Enqueue(value);
//从后面开始移除小于当前值的数字
while(maxQueue.Count > 0 && value > maxQueue.Last.Value){
maxQueue.RemoveLast();
}
maxQueue.AddLast(value);
}
public int Pop_front() {
int val = -1;
if(queue.Count > 0){
val = queue.Dequeue();
if(maxQueue.Count > 0 && val >= maxQueue.First.Value){
maxQueue.RemoveFirst();
}
}
//Console.WriteLine("pop {0}", val);
return val;
}
}
复习代码
csharp
public class MaxQueue {
Queue<int> queue;
LinkedList<int> maxQueue;
public MaxQueue() {
queue = new Queue<int>();
maxQueue = new LinkedList<int>();
}
public int Max_value() {
return maxQueue.Count > 0 ? maxQueue.First.Value : -1;
}
public void Push_back(int value) {
queue.Enqueue(value);
while(maxQueue.Count > 0 && maxQueue.Last.Value < value){
maxQueue.RemoveLast();
}
maxQueue.AddLast(value);
}
public int Pop_front() {
if(queue.Count == 0){
return -1;
}
int value = queue.Dequeue();
if(value == maxQueue.First.Value){
maxQueue.RemoveFirst();
}
return value;
}
}