剑指 Offer 59. 队列的最大值

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列**面试题 59. 队列的最大值 **。

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_valuepush_backpop_front均摊时间复杂度都是O(1)。

若队列为空,pop_frontmax_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

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

这道题目和 用两个栈实现队列 是相似的,先来翻译一下示例一。

["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
这个表示每一次操作的集合函数数组
[[],[1],[2],[],[],[]]
这个表示每一次操作后对应的参数的集合数组

题目要求我们查找最大值 max_value() 的时间复杂度达到 O(1) 级别,借助一个队列肯定是实现不了的,因为需要遍历整个队列才能获取到最大值。

用两个栈实现队列 一文中我们也说过,要想压缩时间得增大空间,即 “空间换时间” ,所以需要再构建一个队列。

为了保证第二个队列可以做到 O(1) 的级别拿到最大值,那么必须是它的队首始终是最大值,也就是说我们需要维护一个递减队列用来保存队列中 所有递减的元素

1、Max_queue

首先初始化,返回 null

剑指 Offer 59. 队列的最大值  .004

2、push_back

参数为 1,此时,两个队列为空,所以 1 入队 queue,同时 1 也入队 deque,返回 null

剑指 Offer 59. 队列的最大值  .006

3、push_back

参数为 2,此时 queuedeque 都有元素了,首先将 2 入队 queue,然后把双端队列 deque 中比 2 小的元素出队,以保持 deque 非单调递减,再把元素 2 入队 deque

剑指 Offer 59. 队列的最大值  .011

4、max_value

直接返回 deque 的队首元素就行。

剑指 Offer 59. 队列的最大值  .013

5、pop_front

queue 的队首元素抛出就行,由于此时抛出的队首元素和 deque 不相等,所以deque 不需要执行任何操作。

剑指 Offer 59. 队列的最大值  .015

5、max_value

直接返回 deque 的队首元素就行。

剑指 Offer 59. 队列的最大值  .017

6、pop_front

为了更好的理解,我们再增加一组 pop_front 操作。

首先,把 queue 的队首元素抛出,由于此时抛出的队首元素和 deque 相等,所以deque 也需要抛出队首元素。

剑指 Offer 59. 队列的最大值  .023

2、规律

每次操作都需要维护好deque,确保它保存队列中 所有递减的元素

3、匹配

  • 队列
  • 双端队列

4、边界

  • 普通队列为空
  • 双端队列为空
  • 双端队列的队首元素和普通队列的队首元素不相等

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 59. 队列的最大值  .002

剑指 Offer 59. 队列的最大值  .003

剑指 Offer 59. 队列的最大值  .004

剑指 Offer 59. 队列的最大值  .005

剑指 Offer 59. 队列的最大值  .006

剑指 Offer 59. 队列的最大值  .007

剑指 Offer 59. 队列的最大值  .008

剑指 Offer 59. 队列的最大值  .009

剑指 Offer 59. 队列的最大值  .010

剑指 Offer 59. 队列的最大值  .011

剑指 Offer 59. 队列的最大值  .012

剑指 Offer 59. 队列的最大值  .013

剑指 Offer 59. 队列的最大值  .014

剑指 Offer 59. 队列的最大值  .015

剑指 Offer 59. 队列的最大值  .016

剑指 Offer 59. 队列的最大值  .017

剑指 Offer 59. 队列的最大值  .018

剑指 Offer 59. 队列的最大值  .019

剑指 Offer 59. 队列的最大值  .020

剑指 Offer 59. 队列的最大值  .021

剑指 Offer 59. 队列的最大值  .022

剑指 Offer 59. 队列的最大值  .023

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
 class MaxQueue {

    // 构建一个普通队列
    Queue<Integer> queue;
    // 构建双端队列
    Deque<Integer> deque;

    public MaxQueue() {
        // 初始化
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    public int max_value() {
        // 如果双端队列为空,返回 -1
        if (deque.isEmpty()){
            return -1;
        }else{
             // 否则返回双端队列的队首元素
            return deque.peekFirst();
        }

    }
    public void push_back(int value) {
         // 普通队列直接添加元素
        queue.add(value);
         // 找出双端队列中那些少于当前元素值的元素
        while(!deque.isEmpty() && deque.peekLast() < value){
              deque.removeLast();
        }
         // 双端队列在尾部添加元素 
        deque.addLast(value);
    }
    public int pop_front() {
        // 如果普通队列为空,返回 -1
        if(queue.isEmpty()) {
            return -1;
        }
        // 如果普通队列的队首元素和双端队列的队首元素相等,那么双端队列也需要移除队首元素
        if(queue.peek().equals(deque.peekFirst())){
            deque.removeFirst();
        }

        // 返回普通队列的队首元素就行了
        return queue.remove();
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(1)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 队列
  • 双端队列

发表评论

邮箱地址不会被公开。 必填项已用*标注