题目描述

  1. 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
  3. 若队列为空，pop_front 和 max_value 需要返回 -1
  5. 示例 1：
  7. 输入: 
  8. ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
  9. [[],[1],[2],[],[],[]]
  10. 输出: [null,null,null,2,1,2]
  11. 示例 2：
  13. 输入: 
  14. ["MaxQueue","pop_front","max_value"]
  15. [[],[],[]]
  16. 输出: [null,-1,-1]
  19. 限制：
  21. 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  22. 1 <= value <= 10^5

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析思路：

O(1)的操作复杂度要求是本题的主要限制
入队出队本身操作并不复杂，主要是如何一直维护这个max number
直觉和经验告诉我可以试试单调栈，但是需要思考确认一下算法正确性

思路是这样的，我用一个普通队列来保存这个最大队列的正常值
然后用一个单调递减的队列来保存队列中出现的最大值，栈顶元素就是目前最大的那个元素
同时也是最先出去被淘汰的的元素

后来仔细发现，题目中的均摊时间复杂度的均摊确实有点意思，就是允许某一步是多次操作，但是这一步操作多次之后带来的收益是后续很多次都不用操作了。

代码

  1. class MaxQueue {
  2. public:
  4.     MaxQueue() {
  6.     }
  8.     int max_value() {
  9.         if(single_stack.empty()) return -1;
  10.         else return single_stack.front();
  11.     }
  13.     void push_back(int value) {
  14.         if(single_stack.empty()){
  15.             single_stack.push_back(value);
  16.         }else{
  17.             while(!single_stack.empty()&&value>single_stack.back()){
  18.                 single_stack.pop_back();
  19.             }
  20.             single_stack.push_back(value);
  21.         }
  22.         que.push(value);
  23.     }
  25.     int pop_front() {
  26.         if(que.empty()) return -1;
  27.         else {
  28.             int top = que.front();
  29.             if(top == single_stack.front()) single_stack.pop_front();
  30.             que.pop();
  31.             return top;
  32.         }
  33.     }
  34. private:
  35.     queue<int> que;
  36.     deque<int> single_stack;
  37. };

复杂度分析

题目已经要求了hhh
image.png