在常数时间内执行Push、Pop和Range操作

Question

在常数时间内执行Push、Pop和Range操作

algorithmdata-structures

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)

- mohit

2

请不要仅仅向我们提出问题并让我们为您解决。请展示给我们您自己尝试解决问题的方法，然后准确地展示结果，并告诉我们为什么您认为它没有起作用。请参阅“你都尝试了什么？”这篇优秀的文章，您真的需要阅读一下。 - John Saunders

Pop() 函数需要找到新的最小值或最大值，这是一个问题 - 目前的实现方式下，Pop() 不是 O(1) 操作。你可以通过向栈中添加信息来解决这个问题 - 栈不一定只包含被推入的元素。 - Michael Burr

@MichaelBurr，是的，这正是我方法的问题。Top是一个“栈”的链表表示。您能否更明确地说明您的建议？ - mohit

@ShashankGupta，是的，我考虑过了。但问题要求O(1)的插入和删除。 - mohit

不，这不是正确的做法。我现在应该给你一个微妙而深刻的提示，让你自己发现一条通往解决方案的路径。但是你可能会在几分钟内得到不止一种可行的解决方案。 - n. m.

显示剩余5条评论

2个回答

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();
    }
  }

- P0W

2

5:30:00Z 和 5:29:49Z。你的评论和我的帖子之间相差11秒，哈哈。 - Byron Lo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Byron Lo · Accepted Answer

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

第一个内部堆栈将表示正在被推入和弹出的“真实”堆栈。

如果新元素大于或等于其顶部的内容，则只会向第二个内部堆栈中推入。

如果新元素小于或等于其顶部的内容，则只会向第三个内部堆栈中推入。

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

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

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