原题（来源Leetcode）
请定义一个队列并实现函数 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的总操作数 <= 100001 <= value <= 10^5
解法
思想
我一开始以为是要手写个堆。。。写完了之后发现自己理解错了题意 : )
就是另外使用一个双向队列维护一个单调递减的队列，如果要弹出的元素也是递减队列的头元素，就把它也弹出。
代码
class MaxQueue {
Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new LinkedList<>();
public MaxQueue() {}
public int max_value() {
if(queue.size() == 0) return -1;
return deque.peek();
}
public void push_back(int value) {
queue.offer(value);
while(deque.size()!=0&&deque.peekLast()<value){
deque.pollLast();
}
deque.offer(value);
}
public int pop_front() {
if(queue.size() == 0) return -1;
int pop = queue.poll();
if(pop == deque.peek()){
deque.poll();
}
return pop;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer59-%e9%98%9f%e5%88%97%e7%9a%84%e6%9c%80%e5%a4%a7%e5%80%bc/
相关推荐
-
拉帮结派的数据结构-并查集
本文参考资源： 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构，又叫“不相交集合”，保持了一组不...
-
leetcode40-组合总和II
原题 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字...
-
leetcode509-斐波那契数
原题 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) ...
-
leetcode122-买卖股票的最佳时机II
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意： 你不能同...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
leetcode771-宝石与石头
原题 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复，J ...
-
剑指offer46-把数字翻译成字符串
原题 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编...
-
leetcode82-删除排序链表中的重复元素II
原题 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示...
-
leetcode1014-最佳观光组合
原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...
-
leetcode86-分隔链表
原题 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head...
