题目链接：点击打开链接
题目大意：略。
解题思路：插入操作虽然看起来有循环，做一个插入操作时最多可能会有 n 次出队操作。但要注意，由于每个数字只会出队一次，因此对于所有的 n 个数字的插入过程，对应的所有出队操作也不会大于 n 次。因此将出队的时间均摊到每个插入操作上，时间复杂度为 O(1)【注意题目说的是“均摊”，而不是最差情况】。
相关企业
字节跳动
AC 代码
Java
// 解决方案(1) class MaxQueue { Queue<Integer> queue; Deque<Integer> deque; public MaxQueue() { queue = new LinkedList<>(); deque = new LinkedList<>(); } public int max_value() { return deque.isEmpty() ? -1 : deque.peekFirst(); } public void push_back(int value) { queue.offer(value); while(!deque.isEmpty() && deque.peekLast() < value) deque.pollLast(); deque.offerLast(value); } public int pop_front() { if(queue.isEmpty()) return -1; if(queue.peek().equals(deque.peekFirst())) deque.pollFirst(); return queue.poll(); } } // 解决方案(2) class MaxQueue { int[] data = new int[10000]; int[] order = new int[10000]; int dHead = -1; int dTail = -1; int oHead = 0; int oTail = -1; public MaxQueue() { } public int max_value() { return order[oHead] == 0 ? -1 : order[oHead]; } public void push_back(int value) { data[++dTail] = value; while (-1 != oTail && order[oTail] != 0 && order[oTail] < value) { order[oTail--] = 0; } order[++oTail] = value; } public int pop_front() { if (dTail == dHead) { return -1; } int res = data[++dHead]; if (res == order[oHead]) { order[oHead++] = 0; } data[dHead] = 0; return res; } }
- C++
class MaxQueue { queue<int> que; deque<int> deq; public: MaxQueue() { } int max_value() { return deq.empty() ? -1 : deq.front(); } void push_back(int value) { que.push(value); while(!deq.empty() && deq.back() < value) deq.pop_back(); deq.push_back(value); } int pop_front() { if(que.empty()) return -1; int val = que.front(); if(val == deq.front()) deq.pop_front(); que.pop(); return val; } };
