关于java:队列的最大值offer59

36次阅读

共计 679 个字符，预计需要花费 2 分钟才能阅读完成。

定义一个队列并实现函数 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]

应用双队列来实现，第一个队列存储压入的数据，进行入队和出队操作，第二个队列实现对最大数值的排序，从队列的尾部开始入队，如果以后值大于队尾的值，则删除尾部的值，直到找到比以后值大的值（即第二队列依据数据程序，删除式地降序排列）。最大值的在第二队列的队首

 一、应用单向队列 + 双向队列：双向数组用来解决 max 值，不便操作，单向数组进行队列的出队和入队
    poll()，peek(),peekFirst(),pollLast()
二、应用数组来解决，应用头尾指针来模仿双向队列
三、应用链表
    1、应用链表须要留神指针的移位，还有就是两个链表的游标在链表为空的时候，须要挪动到链表的表头上去，不然容易有空指针
    对这题来说，链表的操作逻辑有点简单，还是数组好，其次是队列

https://github.com/lunaDolphi…

正文完