剑指 Offer.59-II.队列的最大值
剑指 Offer.59-II.队列的最大值
题目链接 剑指 Offer 59 - II. 队列的最大值
问题描述
请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空,pop_front 和 max_value 需要返回 -1
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
个人想法(模拟) 按照题意在每次调用寻找最大值函数的时候,对整个队列进行扫描,直接返回其中的最大值,与题目中的时间复杂度为O(1)不符合,故本题无法通过模拟来进行解决
官方解法(单调队列)
通过双端队列维护一个,单调的队列,即此队列的元素大小递减,当需要最大元素的时候,直接获取单调队列的队首元素即可,当需要出队时,判断队列当前元素与单调队列队头元素是否相同,若相同,则两个队列都执行出队,否则,执行一个出队即可
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class MaxQueue { Queue<Integer> queue; Deque<Integer> deque; public MaxQueue () { queue = new LinkedList <Integer>(); deque = new LinkedList <Integer>(); } public int max_value () { if (deque.isEmpty()){ return -1 ; }else { return deque.peekFirst(); } } public void push_back (int value) { queue.offer(value); while (!deque.isEmpty() && deque.peekLast() < value){ deque.pollLast(); } deque.offerLast(value); } public int pop_front () { if (queue.isEmpty()) return -1 ; if (queue.peek().equals(deque.peekFirst())){ int res = deque.pollFirst(); queue.poll(); return res; }else { return queue.poll(); } } } 作者:sweetieeyi 链接:https: 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。