图解LeetCode——剑指 Offer 59 - II. 队列
一、题目
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回-1
二、示例
2.1> 示例 1：
【输入】 ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
【输出】 [null,null,null,2,1,2]
2.2> 示例 2：
【输入】 ["MaxQueue","pop_front","max_value"]
[[],[],[]]
【输出】 [null,-1,-1]
限制：
-
1<= push_back，pop_front，max_value的总操作数 <=10000 -
1<= value <=10^5
三、解题思路
根据题目描述，我们需要提供如下3个方法：
【max_value】当前队列中的最大值；
【push_back】向队列末尾添加元素；
【pop_front】从队列头获取元素；
其中，如果假设题目中只要求实现push_back方法和pop_front方法的话，那么本题我们就会非常的简单，就是实现一个简单的队列即可。
而其中比较棘手的就是max_value方法的实现，因为它表示的是当前队列中的最大值。那么我们针对这个最大值，首先会想到两种方式来实现：
【方式1】初始化
max变量，然后每当插入一个元素的时候更新max值，即：max=Math.max(max, value)而这种做法的问题就在于，如果这个最大值出队列了，那么当前队列的最大值就变化了。很显然，不满足题目需求。
【方式2】创建一个集合，每次插入元素的时候，都对其进行排序操作。这种很显然是满足题目要求的，但是明显时间复杂度和空间复杂度都不高。
那么有没有更好的解决办法呢？其实我们可以考虑一个例子，假设我们要分别插入1,7,2这3个数：
【插入数字1】当前最大值为
1；
【插入数字7】当前最大值为7；
【插入数字2】当前最大值为7；
【移除数字1】当前最大值为7；
【移除数字7】当前最大值为2；
从上面的规律中，我们可以看到，无论移除任意元素，最大值都不会是1，原因就是数字1肯定是先于数字7被移除掉了。所以，我们可以采用双向队列结构deque，再根据以下规律，来维护当前最大值：
【情况1】如果
deque为空，则直接执行插入操作；
【情况2】如果deque的末尾元素A小于 待插入元素B，那么元素A出队列；
【情况3】如果deque的末尾元素A大于等于 待插入元素B，那么元素B出队列；
解题思路就如上面所述，下面我们还是按照惯例，举例演示：我们要插入数字1，7，2，4；我们来看一下具体的存储方式。请见下图所示：
四、代码实现
class MaxQueue {
int[] queue;
int head = 0, tail = 0;
Deque<Integer> deque = new ArrayDeque();
public MaxQueue() {
queue = new int[10000];
}
public int max_value() {
return deque.peekFirst() == null ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue[tail++] = value;
if (deque.isEmpty() || deque.peekLast() >= value) {
deque.addLast(value);
return;
}
while (!deque.isEmpty() && deque.peekLast() < value) deque.removeLast();
deque.addLast(value);
}
public int pop_front() {
int num = queue[head] == 0 ? -1 : queue[head++];
if (!deque.isEmpty() && deque.peekFirst() == num) deque.removeFirst();
return num;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
