题目
请定义一个队列并实现函数 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
解析
使用一个List维护最大值
- 判断maxList是否为空并且当前的值是否大于maxList的最后一个值
- 如果满足上述条件，直接循环移除末尾元素
- 直至条件不满足时，将当前值加入到尾部
- 取最大值时直接取下标为0的位置
- 弹出元素时，队列直接弹出，最大值的移除条件（int pop = oriQuene.Dequeue();
if(pop == maxList[0])
maxList.RemoveAt(0);）
代码
public class MaxQueue
{
private Queue<int> oriQuene;
private List<int> maxList;
public MaxQueue() {
oriQuene = new Queue<int>();
maxList = new List<int>();
}
public int Max_value()
{
if (maxList.Count == 0) return -1;
int maxValue = maxList[0];
return maxValue;
}
public void Push_back(int value) {
oriQuene.Enqueue(value);
while (maxList.Count > 0 && maxList[maxList.Count-1]<value)
{
maxList.RemoveAt(maxList.Count-1);
}
maxList.Add(value);
}
public int Pop_front()
{
if (oriQuene.Count == 0) return -1;
int pop = oriQuene.Dequeue();
if(maxList.Count>0&&pop == maxList[0])
maxList.RemoveAt(0);
return pop;
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.Max_value();
* obj.Push_back(value);
* int param_3 = obj.Pop_front();
*/
