LCR 184. 设计自助结算系统

重视自己生命的人，就会重视时间，因为时间不只等于金钱，更等于生命。

题目

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

• get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
• add(value)：将价格为 value 的商品加入待结算商品队列的尾部
• remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1

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

解题思路

• 辅助队列：使用单一队列可以O(1)实现add和remove函数，要实现获取最大值的get_max函数，可使用辅助队列，在入队时，辅助队列先把队尾小于入队元素的出队然后把该元素入队；出队时，若出队元素等于辅助队列队首（也就是最大值）则辅助队列也出队队首元素。

辅助队列 16ms

class Checkout {
    // 队列实现增加和移除操作 同时用辅助队列维护区间最大值
    // 辅助队列：每次入队时，辅助队列入队会先把尾部小于入队的元素弹出
    // 每次出队时，若辅助队列队首也就是最大值等于出队元素，辅助队列也出队
    LinkedList<Integer> list = new LinkedList<>();
    LinkedList<Integer> help = new LinkedList<>();

    public Checkout() {
    }
    
    public int get_max() {
        if(list.size() == 0) return -1;
        return help.peekFirst();
    }
    
    public void add(int value) {
        list.add(value);
        while(help.size() > 0 && help.peekLast() < value) help.removeLast();
        help.add(value);
    }
    
    public int remove() {
        if(list.size() == 0) return -1;
        int h = list.peekFirst();
        if(h == help.peekFirst()) help.removeFirst();
        return list.removeFirst();
    }
}

/**
 * Your Checkout object will be instantiated and called as such:
 * Checkout obj = new Checkout();
 * int param_1 = obj.get_max();
 * obj.add(value);
 * int param_3 = obj.remove();
 */

复杂度分析

• 时间复杂度：O(1)，两个队列的所有元素均最多入队和出队一次，所以时间复杂度均为O(1)。
• 空间复杂度：O(n)，两个队列均使用O(n)的空间。

2023-1-2