Inverview59-2:队列的最大值
《剑指offer》第二版(Python3实现):
https://github.com/NLP-LOVE/CodingInterviews2-ByPython
Inverview59-2:队列的最大值
题目:请定义一个队列并实现函数 max 得到队列里的最大值,要求函数 max、push_back 和 pop_front 的时间复杂度都是 O(1)。也就是对以下函数进行填充并满足要求。
1 2 3 4 5 6 7 8 9 10 11 12
| class MaxQueue:
def __init__(self):
def max_value(self) -> int:
def push_back(self, value: int) -> None:
def pop_front(self) -> int:
|
例如输入,第一个列表表示调用函数的顺序,第二列表示调用函数时所带的参数:
1 2
| ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]]
|
输出为:
解题思路
- 定义两个队列,A 队列存放的是输入的队列,B 队列存放的是可能的最大值队列。
- 例如输入 [2,3,1,2,6,2,5,1] 队列,首先先输入个 2,那么 A 队列里就有 2,B 队列里也是2。
- 然后是输入 3,A 队列就有 [2,3],B 队列里的 2 比 3 小,所以就要把 B 队列清空并赋值 3。
- 接下来输入 1,A = [2,3,1],B队列就要考虑了,因为 1 比 3 小,说明当 A 队列里的 3 出队列之后,后面的 1 有可能是最大值,所以我们要把 1 加入到 B 队列里,接下来依次进行,会发现 B 队列永远都是按照从大到小排序好的。
- 所以,当我们需要 pop_front A队列的时候,就需要比较 A 队列里的第一个元素和 B 队列里的第一个元素,如果相等,删除 B 队列里的头部元素。
以下代码可提交至LeetCode:
https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
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 53 54 55 56 57 58
| class MaxQueue:
def __init__(self): self.queue = [] self.max_queue = []
def max_value(self) -> int: if len(self.queue) == 0: return -1 return self.max_queue[0]
def push_back(self, value: int) -> None: self.queue.append(value)
if len(self.max_queue) == 0: self.max_queue.append(value) else: while len(self.max_queue) != 0 and self.max_queue[-1] < value: self.max_queue.pop() self.max_queue.append(value)
return None
def pop_front(self) -> int: if len(self.queue) == 0: return -1
queue_front = self.queue[0]
if queue_front == self.max_queue[0]: del self.max_queue[0]
del self.queue[0] return queue_front
input_behavior = ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] input_num = [[],[1],[2],[],[],[]] result = []
for i, behavior in enumerate(input_behavior):
if behavior == 'MaxQueue': maxQueue = MaxQueue() result.append(None)
if behavior == 'push_back': result.append(maxQueue.push_back(input_num[i][0]))
if behavior == 'max_value': result.append(maxQueue.max_value())
if behavior == 'pop_front': result.append(maxQueue.pop_front())
print(result)
|
结果如下:
1
| [None, None, None, 2, 1, 2]
|
