6

我在一次采访中被问到这个问题：

设计一个数据结构，允许所有这些操作在常数 , O(1), 时间：

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

我使用带有两个变量max和的自定义堆栈来设计它min，但是在弹出最小或最大元素后这不起作用。

我尝试了什么：

我使用了一个带有两个额外变量 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)
4

2 回答 2

5

实现一个包含范围函数并在内部使用三个堆栈的“堆栈”。

第一个内部堆栈将代表被推送和弹出的“真实”堆栈。

仅当新元素大于或等于其顶部的元素时，才会将第二个内部堆栈推入。

仅当新元素小于或等于其顶部的元素时，才会将第三个内部堆栈推入。

现在，每当您需要计算范围时，只需查看第二个和第三个堆栈的顶部并做一些简单的数学运算。

每当需要将元素从“真实”堆栈中弹出时，请检查该元素是否也在其他两个堆栈的顶部，如果是，则将其从这些堆栈中弹出。

由于您必须以相反的顺序将项目从主堆栈中弹出，因此您永远不会错过其他两个堆栈中的任何内容......这意味着第二个和第三个内部堆栈的顶部将始终是最大值和最小值.

于 2013-10-13T05:30:00.710 回答
1

这类似于 Bryon Lo 的回答，但在他发布之前，我发表了同样的评论

保持 3 堆

  • S1 你的最后筹码
  • S2 和 S3 临时堆栈

休息是不言自明的

  push(T value)
  {
    if (value <= min()) 
    {
        s2.push(value);
    }

    if(value >= max())
    {
        s3.push(value);
    }
    s1.push(value);
  }

 T pop() 
 {
    T value = s1.pop();
    if (value == min()) 
    {
        s2.pop();
    }
    return value;
  }

  T min() 
  {
    if (s2.isEmpty()) 
    {
        return MAX_VALUE;
    } 
    else {
        return s2.peek();
    }
  }

   T max() 
  {
    if (s3.isEmpty()) 
    {
        return MIN_VALUE;
    } 
    else 
    {
        return s3.peek();
    }
  }
于 2013-10-13T05:43:37.607 回答