查找堆栈中的最大值和最小值

Question

假设堆栈中有50000+个整数项？如何有效地找出它的最大值或最小值？ 堆栈可以增长或减少pop（）和push（），但是我们需要跟踪堆栈中的最大值和最小值？

Answer 1

我唯一的想法是继承堆栈并保持最大值和最小值。在弹出和推动做你的最大和最小的变化。

Answer 2

正如Mischel指出的，Stack with find-min/find-max more efficient than O(n)?已经回答了这个问题。

但是，这种回应表明，您需要在堆栈中的每个点上存储每个最大值和最小值。更好的解决方案是为最大值和最小值分别设置一个堆栈。对于最大堆栈，只有当新元素大于当前最大值时，才会将新元素推入最大堆栈，反之亦然。当您弹出主堆栈的元素等于它们并且不等于主堆栈中的下一个元素时，您将弹出最小和最大堆栈的元素。

请注意，这需要O（n）额外的空间，同时提供O（1）操作。