请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1

add(value)：将价格为 value 的商品加入待结算商品队列的尾部

remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1

注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)

示例 1：

输入:

[“Checkout”,“add”,“add”,“get_max”,“remove”,“get_max”]

[[],[4],[7],[],[],[]]

输出: [null,null,null,7,4,7]

示例 2：

输入:

[“Checkout”,“remove”,“get_max”]

[[],[],[]]

输出: [null,-1,-1]

提示：

1 <= get_max, add, remove 的总操作数 <= 10000

1 <= value <= 10^5

与之前单调栈类似，先入队还小的元素可以被挤出

但是先入队的大元素也会先出队，所以我们必须记录后入队的元素，让后入队的大元素挤出先入队的小元素

同时操作队首队尾，需要采用双端队列

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
class Checkout {
public:
    queue<int> q;
    deque<int> maxQ;
    Checkout() {}

    int get_max() {
        if (maxQ.empty())
            return -1;
        return maxQ.front();
    }

    void add(int value) {
        q.push(value);
        while (!maxQ.empty() && maxQ.back() < value) {
            maxQ.pop_back();
        }
        maxQ.push_back(value);
    }

    int remove() {
        if (q.empty())
            return -1;
        int mid = q.front();
        q.pop();
        if (mid == maxQ.front())
            maxQ.pop_front();
        return mid;
    }
};