题目描述：请定义一个队列并实现函数 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的总操作数 <= 10000
- 1 <= value <= 10^5
思考：在一个队列中如何在O(1)时间内找到最大值？并且在最大值出队后，在O(1)时间内找到下一个的最大值？
解题思路：使用一个辅助双端队列doubleQueue，当一个元素value即将入队时，如果doubleQueue队尾元素小于即将入队的value，则将小于value的元素全部出队，再将value入队，否则直接入队，基于该思想，我们维护一个单调的双端队列来保存队列的最大值，辅助队列doubleQueue的队首元素即为队列最大值。
Tips: 数组也支持两端入队和出队，所以直接使用数组也是OK的，只是需要注意的是对数组首元素的操作时数组为了数据对齐，所以会有数据迁移的额外消耗，双端队列可以通过逻辑优化这一点
举个例子，将[1,3,-1,5,7,3]放入队列，求最大值
- 队列中数组data保存所以入队数据，辅助双端队列doubleQueue保存最大值
- 1入队，data和doubleQueue均为空，直接入队，data = [1], doubleQueue = [1]
- 3入队，data = [1,3], doubleQueue中队尾元素1小于3，需出队，3入队，doubleQueue = [3]
- -1入队，data = [1,3,-1], doubleQueue中队尾元素3大于-1，直接入队，doubleQueue = [3,-1]
- 5入队，data = [1,3,-1,5], doubleQueue中队尾元素均小于5，依次从队尾出队，doubleQueue = [5]
- 3入队，data = [1,3,-1,5,7], doubleQueue中队尾元素5小于7，需出队，7入队, doubleQueue = [7]
- 6入队，data = [1,3,-1,5,7,3], doubleQueue中队尾元素7大于3，直接入队，doubleQueue = [7,3]
- 只要data中的7不出队，max_value一直是doubleQueue的队首元素7,当7出队后，队列中的最大值是3
解题开发语言：Swift
// 双端队列
struct DoubleQueue {
private var data = [Int]()
private var n = 0, pre = 0, tra = 0
public var trail: Int? {
return isEmpty ? nil : data[tra - 1]
}
public var prev: Int? {
return isEmpty ? nil : data[pre]
}
public var total: Int {
return tra - pre
}
public var isEmpty: Bool {
return tra - pre == 0
}
init(num: Int) {
n = num
pre = 0
tra = 0
data = [Int](repeating: Int.min, count: num)
}
@discardableResult
public mutating func enqueue(val: Int) -> Bool {
if total == n {
reBuild()
}
// 数组前方有空余空间, 需要做数据搬移
if tra == n && pre > 0 {
for i in pre..<tra {
data[i-pre] = data[i]
}
tra -= pre
pre = 0
}
data[tra] = val
tra += 1
return true
}
@discardableResult
public mutating func enqueueFront(val: Int) -> Bool {
if total == n {
reBuild()
}
pre = pre > 0 ? pre - 1 : 0
data.insert(val, at: pre)
return true
}
@discardableResult
public mutating func dequeue() -> Int? {
if total == 0 {
return nil
}
let val = data[pre]
pre += 1
return val
}
@discardableResult
public mutating func dequeueBack() -> Int? {
if total == 0 {
return nil
}
let val = data[tra - 1]
tra -= 1
return val
}
private mutating func reBuild() {
let count = n * 2
var newData = [Int](repeating: Int.min, count: count)
let range = newData.startIndex..<newData.index(newData.startIndex, offsetBy: n)
newData.replaceSubrange(range, with: data)
data = newData
n = n * 2
}
}
class MaxQueue {
private var data = [Int]()
private var queue: DoubleQueue!
public var isEmpty: Bool {
return data.count == 0
}
init() {
data = [Int]()
queue = DoubleQueue(num: 10)
}
func max_value() -> Int {
if isEmpty {
return -1
}
return queue.prev!
}
func push_back(_ value: Int) {
while (!queue.isEmpty && value > queue.trail!) {
queue.dequeueBack()
}
queue.enqueue(val: value)
data.append(value)
}
func pop_front() -> Int {
if isEmpty {
return -1
}
let val = data.removeFirst()
if val == queue.prev {
queue.dequeue()
}
return val
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* let obj = MaxQueue()
* let ret_1: Int = obj.max_value()
* obj.push_back(value)
* let ret_3: Int = obj.pop_front()
*/
复杂度分析
时间复杂度：O(1), （插入，删除，求最大值），删除操作虽然有while循环，但是一次插入操作最多可能有n次出队操作，需要注意的是每一个元素仅会入队和出队一次，所以n个元素的插入操作，对应的出队操作最多不超过n次，因此将出队的操作均摊到每一次的插入操作上，时间复杂度为O(1)。
空间复杂度：O(n), n为队列存储数据长度，运算中需要额外的辅助双端队列来存储最大值，升序队列需要空间为1，降序队列需要空间为n，平均长度为 n(n+1)/2n = O(n)。
网友评论