专栏首页灵魂画师牧码一道非常经典的队列题

一道非常经典的队列题

队列的最大值

题目来源:剑指offer59

今天发一道剑指offer上面的经典题目,主要考察面试者的知识迁移能力,下面我们先来看一下题目描述。

请定义一个队列并实现函数 max_value 得到队列里的最大值,若队列为空,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]

输入的第一行代表的执行函数,第二行代表的是输入的值,该题中只有我们的push_back传入了参数,输出代表的为执行该函数时,函数的返回值。

个人认为这个题目还是很不错的,而且也有一定的难度,大家可以试着实现一下。

为保证严谨性,文章中的所有代码都经过测试,大家可以放心食用

暴力解法

暴力法,是因为我们的max值通过每次遍历我们的动态数组来获得。思路很简单,我们创建一个动态数组,我们每次执行max_value函数时,通过遍历数组获得最大值,入队操作则用add,出队操作则用remove(0),去除动态数组的头元素。

题目代码:

class MaxQueue {
    //动态数组
    ArrayList<Integer> arr =  new ArrayList<>();
    public MaxQueue() {
       
    }       
    public int max_value() {
         //为空的情况
         if(arr.size() == 0){
           return -1;
         }
         //初始化max
         int max = Integer.MIN_VALUE;
         //遍历动态数组,获取最大值
         for(int i = 0;i<arr.size();i++){
            
            if(arr.get(i)>max){
               max = arr.get(i);
            }

         }
             return max;

    }

    public void push_back(int value) {
        //添加元素
        arr.add(value);   

    }

    public int pop_front() {
        //队列为空时,执行该函数返回-1
       if(arr.size() == 0){
           return -1;
       }else{   
           return arr.remove(0);
       }
      
    }
    
}

利用双端队列

deque (double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。

我们了解了双端队列之后,是不是感觉很实用,很灵活,但实际上在应用程序中远不及栈和队列有用。我们了解双端队列之后,我们来聊一下我们的做题思路吧

这个思路也很简单,我们充分利用双端队列的性质,因为它可以两头出队,那我们在双端队列中仅保存队列中每一段的最大值即可,见下图。

我们分成了三段,第一段的最大值为9,第二段为8,第三段为7。那么我们这个段是怎么分的呢?

我们看第一段最大值为9前面没有其他数字,第二段最大值为8,前面的三个数字都小于8,但是它小于第一段的最大值,同理第三段也是。如果第三段的元素为6,10的话,那我们的双端队列中只有10啦,因为它大于它之前的所有值。

废话不多说下面我们直接看动图吧。

题目代码:

class MaxQueue {

    Queue<Integer> queue ;
    
    Deque<Integer> deque;
    public MaxQueue() {
        queue = new LinkedList<Integer>();
        
        deque = new LinkedList<Integer>();

    }   
    //返回最大值,此时返回的为depue的第一个元素
    public int max_value() {
        if(deque.isEmpty()){
            return -1;
        }
        int max = deque.getFirst();
        return max;
    }
    
    //入队操作
    
    public void push_back(int value) {
    
        //普通队列直接入队
        
        queue.offer(value);
        
        //双端队列需要先将该阶段小于value值的出队
        
        while( !deque.isEmpty() && deque.getLast() < value){
          deque.removeLast();
        }
        
        //入队value
        
        deque.offer(value);
        
    }
    
    //出队操作,返回两种情况,队头小于当前阶段最大值,队头等于当前阶段最大值
    
    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        
        //普通队列出队
        
        int temp = queue.poll();
        
        //判断普通队列和双端队列的队头是否相等,两种返回情况
        if(temp == deque.peekFirst()){
            return deque.pollFirst();
        }
        else{
           return  temp;
        }

    }
}

个人感觉今天的题目很nice,考察范围很广,而且这也是一个面试常考题目

文章分享自微信公众号:
编程如画

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

原始发表时间:2020-11-10
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 一道非常经典的队列题

    今天的题目还是挺有意思的,该题目是剑指offer上面的经典题目,主要考察面试者的知识迁移能力,下面我们先来看一下题目描述。

    公众号袁厨的算法小屋
  • 一道栈和队列的经典题目

    设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5、e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2、e4、e3、e6、e5...

    Jasonangel
  • 一道看似非常难的面试算法题

    这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

    叙帝利
  • 【滑动窗口专题】一道经典的滑动窗口笔试高频题

    这是 LeetCode 上的「438. 找到字符串中所有字母异位词」,难度为「中等」。

    宫水三叶的刷题日记
  • [网络安全] 四十.WHUCTF (3)一道非常有趣的文件上传漏洞题(刀蝎剑详解)

    这道题目有点遗憾没有完成,题目虽然叫“Easy_unserialize”,但我的第一想法是文件上传漏洞,也尝试了很多方法都未成功。下面我将分别从我的解题思路和W...

    Eastmount
  • 讲一道 leetcode 的题

    昨天遇到一道题,经过今天一天的努力总结了出来,这道题太强了,实在忍不住了,就分享出来吧。比较长,从阅读到理解可能得半小时起步了。

    帅地
  • 查找表的经典题

    大家好,我是来自「华为」的「程序员小熊」。清明假期到了,小熊给大家带来一道简单题,让大家放松放松。这道题也是各大厂的面试题,例如苹果、脸书、亚马逊和微软等等。

    程序员小熊
  • 原创 | codeforces 1438D,思路非常非常巧妙的构造题

    今天选择的问题是contest1438的D题,全场通过人数为1325人。一般在codeforces当中千人通过的题难度都不算太高,但是这题有点例外,虽然没有涉及...

    TechFlow-承志
  • 【综合笔试题】难度 2/5,一道笔试 O(nlogn),面试 O(n) 的经典题

    范围内的数不用动。 例如样例中 [3,4,-1,1] 将会被预处理成 [1,-1,3,4]。

    宫水三叶的刷题日记
  • 从一道「回溯算法」经典题与你分享回溯算法的基本套路 ..

    这是 LeetCode 上的「17. 电话号码的字母组合」,难度为 Medium。

    宫水三叶的刷题日记
  • 一道经典的JS面试题

    原理:当复杂类型数据与基本类型数据作比较时会发生隐性转换,会调用toString()或者valueOf()方法

    越陌度阡
  • 一道SQL题的多种解法

    自然的想法,寻找每个店铺是否连续三天都有销售额。利用现有的表,构造一个中间表,中间表既有当前日期的销售额,又有当前日期后两天的销售额,然后筛选销售额大于0的店铺...

    数据森麟
  • 一道快速排序题的解析

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

    大黄大黄大黄
  • 一道shell脚本的统计题

    a. 若干行数据,每行数据有3列内容,列之间\t分割。 b. 第一列表示属性1,第二列表示属性2,第三列表示属性3。 c. 每一个属性的可能取...

    用户3147702
  • 一道有趣的树状数组题

    Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social ga...

    ACM算法日常
  • 一道有趣的 Java 基础题

    在一个 Java 群里有位群友分享了一道关于 Java 的题目,问代码是否抛异常。代码如下:

    码农UP2U
  • 记Javascript一道题的理解

    代码如下: function Foo(){ getName = function(){ console.log("1"); } return t...

    sam dragon
  • 一道位运算的算法题

    一组整数,除了一个只出现一次以外,其他每个整数都恰好出现三次,要寻找那个特殊的整数。

    四火
  • 一道简单的Python编程题

    作者: zifanwang  发布于2020-07-05

    zifan

扫码关注腾讯云开发者

领取腾讯云代金券