推,弹,范围恒定时间

Question

我在接受采访时被问到这个问题:

设计一个数据结构,允许所有这些操作保持不变O(1),时间:

• 推一个元素
• 弹出一个元素
• 元素范围:查找当前元素的最小间隔范围.
  例如.范围[1, 22, 44, 56, 99, 98, 56]是98.

我设计的这个使用定制的堆栈两个变量,max并且min,但这并不Pop'ing一个最小或最大元素之后的工作.

我尝试了什么:

我使用了一个带有两个额外变量max和min的堆栈:

DS 
{
 top, //Top of the Stack 
 min, //Min till now
 max  //Max till now
}

Push(DS, elem)
  Push_Stack(DS.top, elem)
  if elem < DS.min
    DS.min = elem
  if elem > DS.max
    DS.max = elem

Range(DS)
 return DS.max - DS.min

Pop(DS)
  x = Pop_Stack(DS.top)
  if (x == DS.min)
    DS.min = Find_New_Min(DS.top) //This takes linear time using this approach
  if (x == DS.max)
    DS.max = Find_New_Max(DS.top)

Answer 1

实现包含范围函数的"堆栈"并在内部使用三个堆栈.

第一个内部堆栈将代表被推送和弹出的"真实"堆栈.

如果新元素大于或等于其上的内容,则仅推送第二个内部堆栈.

如果新元素小于或等于其上的元素,则仅推送第三个内部堆栈.

现在,无论何时需要计算范围,只需查看第二个和第三个堆栈的顶部并进行一些简单的数学运算.

每当元素需要从"真实"堆栈中弹出时,检查元素是否也位于其他两个堆栈的顶部,如果是,则将其从这些堆栈中弹出.

因为你必须以相反的顺序从主堆栈中弹出项目,所以你不会错过其他两个堆栈中的任何东西......这意味着第二个和第三个内部堆栈的顶部将始终是最大值和最小值.