使用find分钟/找到-MAX比O（n）的更有效的堆栈？ [英] Stack with find-min/find-max more efficient than O(n)?

问题描述

我感兴趣的创建类似堆栈支持以下操作的Java数据结构，尽可能有效地：

I am interested in creating a Java data structure similar to a stack that supports the following operations as efficiently as possible:

• 一键，还增加了一个新的元素堆顶上，
• 流行音乐，这消除了堆栈顶部元素
• 找到-Max的，它返回（但不删除）堆栈的最大元素，而
• 找到民，返回（但不删除）堆栈的最小元素，而

什么是最快的实现这个数据结构的？我怎么可能去写它的Java？

What would be the fastest implementation of this data structure? How might I go about writing it in Java?

推荐答案

这是一个经典的数据结构的问题。问题背后的直觉是如下 - 的唯一方法是，如果你把一个新的值压入堆栈或弹出一个新的值从堆栈的最大和最小可改变的是。鉴于这一点，假设在堆栈中的各个级别您记录的最高和最低值的在等于或低于该堆栈中点。然后，当你把一个新的元素压入堆栈，你可以很容易地（在O（1）时间）通过比较你刚才推到了当前的最大值和最小值的新元素计算的最大值和最小值在堆栈中的任何位置。同样，当爆开的元件，你会暴露在堆栈一步下面的顶部，已经有在堆栈存储沿着它的其余部分的最大和最小值的元素

This is a classic data structures question. The intuition behind the problem is as follows - the only way that the maximum and minimum can change is if you push a new value onto the stack or pop a new value off of the stack. Given this, suppose that at each level in the stack you keep track of the maximum and minimum values at or below that point in the stack. Then, when you push a new element onto the stack, you can easily (in O(1) time) compute the maximum and minimum value anywhere in the stack by comparing the new element you just pushed to the current maximum and minimum. Similarly, when you pop off an element, you will expose the element in the stack one step below the top, which already has the maximum and minimum values in the rest of the stack stored alongside it.

在视觉上，假设我们有一个堆栈和添加的顺序值2,7，1,8，3，和9。我们开始推2，所以我们推2到我们的堆栈。由于2现在是在栈中的最大和最小值，以及，我们记录如下：

Visually, suppose that we have a stack and add the values 2, 7, 1, 8, 3, and 9, in that order. We start by pushing 2, and so we push 2 onto our stack. Since 2 is now the largest and smallest value in the stack as well, we record this:

 2  (max 2, min 2)

现在，让我们来推7.自7比2（当前最大），我们结束了这一点：

Now, let's push 7. Since 7 is greater than 2 (the current max), we end up with this:

 7  (max 7, min 2)
 2  (max 2, min 2)

注意，现在我们可以通过查看在堆栈的顶部，并看到了7是max和2是最小读出堆栈的最大和最小。如果我们现在推1，我们得到

Notice that right now we can read off the max and min of the stack by looking at the top of the stack and seeing that 7 is the max and 2 is the min. If we now push 1, we get

 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

在这里，我们知道，1是最小的，因为我们可以比较1存储堆栈（2）之上的缓存最小值。作为练习，一定要了解为什么添加8,3和9后，我们得到这样的：

Here, we know that 1 is the minimum, since we can compare 1 to the cached min value stored atop the stack (2). As an exercise, make sure you understand why after adding 8, 3, and 9, we get this:

 9  (max 9, min 1)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

现在，如果我们想查询的最大值和最小值，我们可以在O（1）通过阅读过的存储最大和最小的堆栈（9和1，分别）之上这么做。

Now, if we want to query the max and min, we can do so in O(1) by just reading off the stored max and min atop the stack (9 and 1, respectively).

现在，假设我们流行过的顶级元素。这产生图9和修改栈是

Now, suppose that we pop off the top element. This yields 9 and modifies the stack to be

 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

而现在注意到，这些元素的最大值为8，完全正确的答案！如果我们再攀新高0，我们会得到这样的：

And now notice that the max of these elements is 8, exactly the correct answer! If we then pushed 0, we'd get this:

 0  (max 8, min 0)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

而且，正如你所看到的，最大值和最小值的计算正确。

And, as you can see, the max and min are computed correctly.

总的来说，这导致了有O（1）推入，弹出栈的实现，找到-MAX，并找到分钟，这是因为它得到的渐近好。我会离开的实现作为一个练习。 :-)然而，你可能要考虑执行使用标准的协议栈的实现技术，如使用的动态数组或链接列表对象，其每一个存放堆栈元件，最小值和最大值。您可以通过的ArrayList 或的LinkedList 的利用脱做到这一点很容易。或者，你可以使用提供的Java 堆栈类，但IIRC它有一些开销，由于同步可能是不必要的这种应用。

Overall, this leads to an implementation of the stack that has O(1) push, pop, find-max, and find-min, which is as asymptotically as good as it gets. I'll leave the implementation as an exercise. :-) However, you may want to consider implementing the stack using one of the standard stack implementation techniques, such as using a dynamic array or linked list of objects, each of which holds the stack element, min, and max. You could do this easily by leveraging off of ArrayList or LinkedList. Alternatively, you could use the provided Java Stack class, though IIRC it has some overhead due to synchronization that might be unnecessary for this application.

有趣的是，一旦你建立了一个堆栈具有这些特性，你可以使用它作为构建模块来构建<一个href="http://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-constan/4802260#4802260">a排队具有相同属性和时间保障。也可以用它在一个更复杂的结构，以建立一个双向队列具有这些性能，以及

Interestingly, once you've built a stack with these properties, you can use it as a building block to construct a queue with the same properties and time guarantees. You can also use it in a more complex construction to build a double-ended queue with these properties as well.

希望这有助于！

编辑：：如果您感到好奇，我有的一分钟堆栈 和前述的的分钟队列 在我的个人网站。希望这展示了什么，这可能看起来像在实践中！

If you're curious, I have C++ implementations of a min-stack and a the aforementioned min-queue on my personal site. Hopefully this shows off what this might look like in practice!

这篇关于使用find分钟/找到-MAX比O（n）的更有效的堆栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！