使用 find-min/find-max 堆栈比 O(n) 更有效?

2022-01-22 00:00:00 algorithm data-structures big-o stack java

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

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

  • Push，在栈顶添加一个新元素，
  • 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) 的 push、pop、find-max 和 find-min，它尽可能地渐近.我将把实现留作练习.:-) 但是，您可能需要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用 动态数组或链表对象，每个对象都包含堆栈元素，最小值和最大值.您可以利用 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-stack 和前面提到的 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!

相关文章