【Leetcode Daily】184设计自助结算系统

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是设计一个类，类中能够存储价格队列，并能随时提取其中最大值，要求加入值，弹出值和取最大值的时间复杂度均为 O(1)

思路分享

• 入队出队对于普通的队列都是 O(1) 复杂度，所以只要解决从队列中提取最大值为 O(1) 复杂度即可。

• 解决这个问题，只要同时引入单调队列维护最大值即可，如果只用一个变量维护最大值，在最坏情况下仍是 O(n) 复杂度。

• 删除队列的元素时，由于单调队列只会降序保存大值，不需要担心顺序错位，毕竟队列按顺序弹值也一定让单调队列按顺序弹值。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Checkout:

    def __init__(self):
        self.max_q = deque()
        self.q = deque()

    def get_max(self) -> int:
        return self.max_q[0] if self.max_q else -1
        

    def add(self, value: int) -> None:
        self.q.append(value)
        while self.max_q and value > self.max_q[-1]:
            self.max_q.pop()
        self.max_q.append(value)

    def remove(self) -> int:
        v = self.q.popleft() if self.q else -1
        if v != -1 and v == self.max_q[0]:
            self.max_q.popleft()
        return v


# Your Checkout object will be instantiated and called as such:
# obj = Checkout()
# param_1 = obj.get_max()
# obj.add(value)
# param_3 = obj.remove()