设计一个支持O(1)时间获取最大值的队列

题目描述
设计一个队列，除了支持队列的基本操作（入队、出队）外，还需要支持在常数时间O(1)内获取队列中的最大值。

解题思路
这个问题的难点在于队列是先进先出的数据结构，而最大值会随着元素的入队和出队动态变化。我们需要一种能够高效跟踪当前队列最大值的方法。

解决方案
我们可以使用两个栈来模拟队列，因为栈更容易实现O(1)获取最大值。具体来说，我们使用一个"最大值栈"的技术。

实现步骤

1. 数据结构设计

   • 使用两个栈：stackIn（用于入队）和stackOut（用于出队）
   • 每个栈不仅存储元素值，还存储当前栈的最大值

2. 定义栈节点结构
   每个栈节点包含两个值：

   • value: 元素的实际值
   • max: 从栈底到当前节点的最大值

class MaxStackNode:
    def __init__(self, value, current_max):
        self.value = value
        self.current_max = current_max

3. 具体操作实现

入队操作（enqueue）

• 直接将元素压入stackIn栈
• 对于每个新元素，计算从栈底到当前位置的最大值

def enqueue(self, value):
    # 如果stackIn为空，当前最大值就是value本身
    if not self.stackIn:
        current_max = value
    else:
        # 否则，当前最大值是value和栈顶元素最大值的较大者
        current_max = max(value, self.stackIn[-1].current_max)
    
    # 创建新节点并压入stackIn
    new_node = MaxStackNode(value, current_max)
    self.stackIn.append(new_node)

出队操作（dequeue）

• 如果stackOut为空，需要将stackIn中的所有元素转移到stackOut
• 然后从stackOut弹出栈顶元素

def dequeue(self):
    if self.empty():
        return None
    
    # 如果stackOut为空，需要转移元素
    if not self.stackOut:
        self._transfer_elements()
    
    # 从stackOut弹出元素
    return self.stackOut.pop().value

def _transfer_elements(self):
    """将stackIn中的所有元素转移到stackOut"""
    current_max = None
    
    # 逐个转移元素
    while self.stackIn:
        node = self.stackIn.pop()
        value = node.value
        
        # 计算stackOut中当前的最大值
        if current_max is None:
            current_max = value
        else:
            current_max = max(value, current_max)
        
        # 创建新节点并压入stackOut
        new_node = MaxStackNode(value, current_max)
        self.stackOut.append(new_node)

获取最大值操作（get_max）

• 比较stackIn和stackOut的当前最大值，取较大者

def get_max(self):
    if self.empty():
        return None
    
    max1 = self.stackIn[-1].current_max if self.stackIn else float('-inf')
    max2 = self.stackOut[-1].current_max if self.stackOut else float('-inf')
    
    return max(max1, max2)

4. 辅助方法

def empty(self):
    return not self.stackIn and not self.stackOut

def size(self):
    return len(self.stackIn) + len(self.stackOut)

时间复杂度分析

• 入队：O(1) - 直接压栈
• 出队：摊还时间复杂度O(1) - 每个元素最多被转移一次
• 获取最大值：O(1) - 比较两个栈的最大值

完整代码示例

class MaxStackNode:
    def __init__(self, value, current_max):
        self.value = value
        self.current_max = current_max

class MaxQueue:
    def __init__(self):
        self.stackIn = []  # 用于入队的栈
        self.stackOut = []  # 用于出队的栈
    
    def enqueue(self, value):
        # 计算当前最大值
        if not self.stackIn:
            current_max = value
        else:
            current_max = max(value, self.stackIn[-1].current_max)
        
        new_node = MaxStackNode(value, current_max)
        self.stackIn.append(new_node)
    
    def dequeue(self):
        if self.empty():
            return None
        
        if not self.stackOut:
            self._transfer_elements()
        
        return self.stackOut.pop().value
    
    def _transfer_elements(self):
        current_max = None
        
        while self.stackIn:
            node = self.stackIn.pop()
            value = node.value
            
            if current_max is None:
                current_max = value
            else:
                current_max = max(value, current_max)
            
            new_node = MaxStackNode(value, current_max)
            self.stackOut.append(new_node)
    
    def get_max(self):
        if self.empty():
            return None
        
        max1 = self.stackIn[-1].current_max if self.stackIn else float('-inf')
        max2 = self.stackOut[-1].current_max if self.stackOut else float('-inf')
        
        return max(max1, max2)
    
    def empty(self):
        return not self.stackIn and not self.stackOut
    
    def size(self):
        return len(self.stackIn) + len(self.stackOut)

测试示例

# 测试代码
mq = MaxQueue()
mq.enqueue(3)
mq.enqueue(1)
mq.enqueue(4)
print(mq.get_max())  # 输出: 4

mq.enqueue(2)
print(mq.get_max())  # 输出: 4

mq.dequeue()  # 移除3
print(mq.get_max())  # 输出: 4

mq.dequeue()  # 移除1
print(mq.get_max())  # 输出: 4

mq.dequeue()  # 移除4
print(mq.get_max())  # 输出: 2

关键点总结

1. 使用两个栈模拟队列，分别处理入队和出队操作
2. 每个栈节点记录从栈底到当前位置的最大值
3. 获取最大值时，比较两个栈的当前最大值
4. 在出队时，如果出队栈为空，需要一次性将入队栈的所有元素转移

这种方法巧妙地利用了栈的特性，在保证所有操作都是O(1)时间复杂度的情况下，实现了队列的最大值查询功能。