题目

题目地址：

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

题目描述：

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

思路

第一个想法

测试用例

  • 边界条件

参考：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/ru-he-jie-jue-o1-fu-za-du-de-api-she-ji-ti-by-z1m/

程序

辅助队列

max_value：O(1)，直接返回双端队列（或数组）头部的元素。
pop_front：O(1)，从队列中弹出一个元素，仍然是常数时间复杂度。

push_back：O(1)，例如 543216，只有最后一次 push_back 操作是 O(n)，其他每次操作的时间复杂度都是 O(1)，均摊时间复杂度为 O(1)×(n−1)+O(n))/n=O(1)。

  1. class MaxQueue:
  2.     def __init__(self):
  3.         self.__queue = []
  4.         self.__temp_queue = []
  6.     def max_value(self) -> int:
  7.         if self.__temp_queue:
  8.             return self.__temp_queue[0]
  9.         else:
  10.             return -1
  12.     def push_back(self, value: int) -> None:
  13.         self.__queue.append(value)
  14.         while self.__temp_queue and self.__temp_queue[-1] < value:
  15.             self.__temp_queue.pop()
  16.         self.__temp_queue.append(value)
  19.     def pop_front(self) -> int:
  20.         if not self.__queue:
  21.             return -1
  22.         if self.__queue[0] == self.__temp_queue[0]:
  23.             self.__temp_queue.pop(0)
  24.         return self.__queue.pop(0)
  28. # Your MaxQueue object will be instantiated and called as such:
  29. # obj = MaxQueue()
  30. # param_1 = obj.max_value()
  31. # obj.push_back(value)
  32. # param_3 = obj.pop_front()

相似题目