问题描述
我有兴趣创建一个类似于堆栈的 Java 数据结构，它尽可能高效地支持以下操作:
I am interested in creating a Java data structure similar to a stack that supports the following operations as efficiently as possible:
- 推送，在堆栈顶部添加一个新元素，
- Pop，移除栈顶元素，
- Find-Max，返回(但不移除)堆栈中最大的元素，以及
- Find-Min，返回(但不移除)堆栈中的最小元素，以及
这种数据结构最快的实现是什么?我该如何用 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 是最大值而 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) 的推送、弹出、查找最大值和查找最小值，这与它得到的一样渐近.我将把实现作为练习.:-) 但是，您可能需要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用 动态数组 或链接列表 对象，每个对象都保存堆栈元素，最小值和最大值您可以通过利用 ArrayList 或 LinkedList 轻松完成此操作.或者，您可以使用提供的 Java Stack 类，尽管 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.
有趣的是，一旦您构建了具有这些属性的堆栈，您就可以将其用作构建块来构建 具有相同属性的队列和时间保证.您还可以在更复杂的构造中使用它来构建具有这些属性的双端队列.
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.
希望这有帮助！
如果您好奇，我有 一个最小栈 和前面提到的min-queue 在我的个人网站上.希望这展示了它在实践中的样子！
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-min/find-max 堆栈比 O(n) 更有效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！