难度: Medium
请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：
get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1add(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 的总操作数 <= 100001 <= value <= 10^5运行时间: 404 ms
内存: 18.5 MB
class Checkout:
def __init__(self):
# 2个数组
self.queue = []
self.max_stack = []
def get_max(self) -> int:
if self.max_stack:
return self.max_stack[0]
else:
return -1
def add(self, value: int) -> None:
self.queue.append(value)
while self.max_stack and self.max_stack[-1] < value:
self.max_stack.pop()
self.max_stack.append(value)
def remove(self) -> int:
if not self.queue:
return -1
ans = self.queue.pop(0)
if ans == self.max_stack[0]:
self.max_stack.pop(0)
return ans
# Your Checkout object will be instantiated and called as such:
# obj = Checkout()
# param_1 = obj.get_max()
# obj.add(value)
# param_3 = obj.remove()
该题解通过使用两个数组（queue 和 max_stack）来实现一个自助结账系统。queue 用于正常队列操作，存储加入的商品价格。max_stack 用于维护当前队列中所有未被移除的商品的最大价格，确保 get_max() 能以 O(1) 的时间复杂度运行。在 add 操作中，会将小于新加入值的元素从 max_stack 中移除，以保持 max_stack 的第一个元素始终是当前队列中的最大值。remove 操作中，若移除的元素是当前最大值（即 max_stack 的首元素），则同时从 max_stack 中移除这个元素。
时间复杂度: O(1) 均摊
空间复杂度: O(n)
# 类定义
class Checkout:
def __init__(self):
self.queue = [] # 用于存储所有待结算商品的价格
self.max_stack = [] # 用于维护当前未被移除商品的最大价格
def get_max(self) -> int:
# 如果 max_stack 非空，返回队列中的最大值
if self.max_stack:
return self.max_stack[0]
# 如果队列为空，返回 -1
else:
return -1
def add(self, value: int) -> None:
self.queue.append(value) # 将新商品加到队列末尾
# 移除所有小于新商品价格的元素以维护 max_stack 的正确性
while self.max_stack and self.max_stack[-1] < value:
self.max_stack.pop()
# 将新商品价格加到 max_stack
self.max_stack.append(value)
def remove(self) -> int:
if not self.queue:
return -1 # 队列为空时直接返回 -1
ans = self.queue.pop(0) # 移除队列中的第一个商品
# 如果移除的商品是当前最大值，也从 max_stack 中移除
if ans == self.max_stack[0]:
self.max_stack.pop(0)
return ans # 返回被移除的商品价格
在`add`操作中，移除`max_stack`中所有小于新商品价格的元素是为了维护`max_stack`的性质，即`max_stack`的第一个元素总是当前队列中的最大值。这样做确保了`get_max()`操作可以在常数时间内完成。当一个新的更大的元素被添加到队列中时，所有比它小的元素不会再是最大元素，因此从`max_stack`中移除这些元素可以保持栈的有效性和更新队列的最大值。
在`remove`操作中，如果移除的元素不是`max_stack`中的首元素，这意味着移除的元素小于当前队列的最大值。在这种情况下，`max_stack`不需要更新，因为移除的元素并不影响队列中的最大值。`max_stack`的首元素仍然是队列中的最大值，因此保持不变。
当所有商品价格相同时，每次`add`操作添加的元素都与`max_stack`中的元素相等。在这种情况下，每个元素都需要被添加到`max_stack`中，因为每个元素都可能成为队列中的最大值。因此，`max_stack`将包含与队列长度相同数量的元素，每个都是相同的最大值。在`remove`操作中，每次移除队列和`max_stack`的首元素。