如何有效地删除堆栈数据结构中低于阈值的值？

Question

我正在尝试实现一个支持以下操作的堆栈：

push： 将整数值推入堆栈顶部。 pop：从堆栈中删除顶部元素。 remove_lower value： 移除栈中所有小于value的元素。 remove_upper value：移除栈中所有大于value的元素。

我需要确保所有操作都是高效的，特别是考虑到堆栈的潜在大小。

我考虑使用 TreeMap 按排序顺序管理元素并存储它们的计数，但我正在努力有效地结合阈值删除来处理堆栈的“后进先出”（LIFO）行为。

问题：
TreeMap和堆栈的同步：TreeMap有效地跟踪元素以进行基于阈值的删除，但它不直接更新堆栈结构。
效率：从 TreeMap 和堆栈中删除元素同时保持可接受的时间复杂度被证明是具有挑战性的。

问题：
如何在remove_lower和remove_upper操作期间有效同步TreeMap和堆栈？
考虑到堆栈行为（推送/弹出）和基于阈值的删除要求，是否有更好的数据结构或方法可以有效地处理此问题？

Answer 1

当您使用的堆栈实际上只能执行压入和弹出操作时，在“删除较低”操作期间您需要第二个堆栈，以临时存储您不想删除的弹出值。然而，这只是一个学术练习。

对于现实世界的问题，您可以使用，例如

ArrayDeque

。它支持

push

和

pop

，但您也可以拨打电话，例如

stack.removeIf(element -> element < threshold);

，就这样吧。

这已经相当有效了。维护额外的数据结构（例如

TreeMap

）几乎没有什么好处。它唯一可以告诉您的是，是否没有元素低于阈值，因此在这种情况下您可以跳过

removeIf

。但代价是必须在每个

push

和

pop

上更新地图，而如果有元素需要删除，则不会获得任何东西。在大多数情况下，这些额外成本将超过收益。