难度: Hard
Submission
运行时间: 318 ms
内存: 64.8 MB
class MaxStack:
def __init__(self):
self.heap = []
self.stack = []
self.del_heap = set()
self.del_stack = set()
self.value_idx = {}
def push(self, val):
if val not in self.value_idx:
self.value_idx[val] = -1
self.value_idx[val] += 1
heapq.heappush(self.heap, (-val, -self.value_idx[val]))
self.stack.append((val, self.value_idx[val]))
def pop(self):
val_idx = self.stack.pop()
while val_idx in self.del_stack:
self.del_stack.remove(val_idx)
val_idx = self.stack.pop()
self.del_heap.add(val_idx)
return val_idx[0]
def top(self):
while self.stack[-1] in self.del_stack:
self.del_stack.remove(self.stack[-1])
self.stack.pop()
return self.stack[-1][0]
def peekMax(self):
val, idx = self.heap[0]
while (-val, -idx) in self.del_heap:
self.del_heap.remove((-val, -idx))
heapq.heappop(self.heap)
val, idx = self.heap[0]
return -val
def popMax(self):
val, idx = heapq.heappop(self.heap)
while (-val, -idx) in self.del_heap:
self.del_heap.remove((-val, -idx))
val, idx = heapq.heappop(self.heap)
self.del_stack.add((-val, -idx))
return -val
Explain
该题解实现了一个最大栈的数据结构，可以在常数时间内访问栈顶元素、插入、删除以及获取最大元素。这通过维护一个正常的栈来存储元素，一个最大堆来快速获取最大值，和两个集合来记录已经从栈和堆中逻辑删除（但物理未删除）的元素来实现。为了处理堆中可能存在的重复元素，还使用了一个字典来记录每个值的索引，确保每个元素在堆中都是唯一的。
时间复杂度: O(log n)
空间复杂度: O(n)
class MaxStack:
def __init__(self):
self.heap = [] # 堆，用于快速获取最大值
self.stack = [] # 栈，用于常规的栈操作
self.del_heap = set() # 记录堆中逻辑删除的元素
self.del_stack = set() # 记录栈中逻辑删除的元素
self.value_idx = {} # 记录每个值的索引，确保堆中的唯一性
def push(self, val):
if val not in self.value_idx:
self.value_idx[val] = -1
self.value_idx[val] += 1
heapq.heappush(self.heap, (-val, -self.value_idx[val])) # 使用负值确保堆为最大堆
self.stack.append((val, self.value_idx[val])) # 同时将元素和索引信息保存在栈中
def pop(self):
val_idx = self.stack.pop()
while val_idx in self.del_stack:
self.del_stack.remove(val_idx)
val_idx = self.stack.pop()
self.del_heap.add(val_idx)
return val_idx[0]
def top(self):
while self.stack[-1] in self.del_stack:
self.del_stack.remove(self.stack[-1])
self.stack.pop()
return self.stack[-1][0]
def peekMax(self):
val, idx = self.heap[0]
while (-val, -idx) in self.del_heap:
self.del_heap.remove((-val, -idx))
heapq.heappop(self.heap)
val, idx = self.heap[0]
return -val
def popMax(self):
val, idx = heapq.heappop(self.heap)
while (-val, -idx) in self.del_heap:
self.del_heap.remove((-val, -idx))
val, idx = heapq.heappop(self.heap)
self.del_stack.add((-val, -idx))
return -val
Explore
在`popMax`和`pop`操作中，为了保持堆和栈的数据同步，使用了逻辑删除的方法。当从栈中弹出元素时，将其添加到`del_heap`集合中表示该元素在堆中也需要被逻辑删除。类似地，当从堆中弹出元素时，将其添加到`del_stack`集合中表示该元素在栈中也需要被逻辑删除。在任何访问堆顶或栈顶的操作中，都会检查当前元素是否存在于相应的逻辑删除集合中，并进行相应的调整，以确保返回的值是有效的最大值或栈顶值，从而实现堆和栈的数据一致性。
在Python中，标准库提供的堆（heapq）默认是最小堆，即堆顶是最小元素。为了实现最大栈的功能，需要快速访问最大元素，因此需要构建一个最大堆。通过将所有元素取负，原本较大的数变为较小的负数，这样就可以利用最小堆的性质反向实现最大堆的效果。选择使用负值而不直接用最小堆的API是因为Python标准库中没有直接提供最大堆的实现，使用负值是一种简便且有效的方法来借用最小堆实现最大堆功能。
使用`del_heap`和`del_stack`两个集合来记录逻辑删除的元素是为了优化操作的时间复杂度。直接物理删除元素（例如从堆中删除特定元素）通常需要O(n)的时间复杂度，因为需要重新构造堆以保持其性质。通过标记逻辑删除，我们可以延迟这一过程，只有在必要时（如访问最大元素或弹出操作时发现堆顶或栈顶元素已被逻辑删除）才进行堆的调整或栈的清理。这种方法允许大多数操作保持较低的时间复杂度，提高了整体性能。