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

问题描述

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

• 推，在堆栈顶部添加一个新元素，


• Pop，它删除堆栈的顶部元素


• Find-Max，返回（但不删除）堆栈的最大元素，而


• Find-Min返回（但不会除去）栈的最小元素，而

这个数据结构的最快实现是什么？我如何用Java编写它？

解决方案

这是一个经典的数据结构问题。问题背后的直觉如下 - 最大值和最小值可以改变的唯一方法是将新值推入堆栈或从堆栈中弹出一个新值。给定这一点，假设在堆栈中的每个级别，您可以跟踪堆栈中该点以下的最大值和最小值。然后，当您将新元素推入堆栈时，您可以轻松（在O（1）时间内）通过将刚被推送的新元素与当前最大值和最小值进行比较来计算堆栈中的任何位置的最大值和最小值。类似地，当你弹出一个元素时，你将把堆栈中的元素暴露在顶部的一个步骤之下，这个元素在堆栈的其余部分中已经有最大值和最小值。

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

  2（最大2，最小2 ）
  

现在，我们来推7.由于7大于2（当前最大值），我们结束这样：

  7（最多7，最少2）
 2（最多2，最小2）$ b请注意，现在我们可以通过查看堆栈的顶部来读取堆栈的最大值和最小值。并且看到7是最大值，2是最小值。如果我们现在推1，我们得到
  1（最多7，最小1）
 7（最多7分钟2）
 2（最大2，最小2）
  
这里，我们知道1是最小值，因为我们可以将1与存储在堆栈顶部的缓存最小值进行比较（2）。作为一个练习，确保你明白为什么在添加8，3和9之后，我们得到：
  9（最多9 ，最小1）
 3（最多8，最小1）
 8（最多8，最小1）
 1（最多7，最小1）
 7（最多7分钟2）
 2（最大2，最小2）
  
现在，如果我们要查询最大和最小，我们可以通过在堆栈顶部读取存储的最大值和最小值（分别为9和1）来执行O（1）。
 
 
 
假设我们弹出顶部元素。这产生9并修改堆栈为
  3（最多8，最小1）
 8（最多8，最小1）
 1（最多7，最小1）
 7（最多7，最小2）
 2（最大2，最小2）
 现在注意到这些元素的最大值是8，正确的答案是正确答案！
如果我们按0，我们会得到这样的：
  0（最多8，最小0）
 3最大8，最小1）
 8（最多8，最小1）
 1（最大7，最小1）
 7（最多7，最小2）
 2 ，min 2）
  
而且，你可以看到，最大和最小是正确计算的。总而言之，这导致了具有O（1）push，pop，find-max和find-min的堆栈的实现，其像渐进式一样好得到我将把实施作为一个练习。 :-)但是，您可能希望考虑使用标准堆栈实现技术之一来实现堆栈，例如使用动态数组或链接列表，每个对象保存堆栈元素， min，最大您可以通过利用 ArrayList 或 LinkedList 轻松实现。或者，您可以使用提供的Java 堆栈类，尽管IIRC由于同步可能会有一些开销，这可能对此应用程序是不必要的。
 
 
 
有趣的是，一旦你构建了一个这些属性的堆栈，你可以使用它作为一个构建块来构造具有相同属性的队列和时间保证。您也可以在更复杂的结构中使用它来构建具有这些属性的双端队列。
 
 
 
希望这有帮助！
 
 
 
 编辑：如果你好奇，我有C ++实现的 最小堆栈 和上述 最小队列 。希望这样可以显示这在实践中看起来如何！
 
I am interested in creating a Java data structure similar to a stack that supports the following operations as efficiently as possible:


Push, which adds a new element atop the stack,
Pop, which removes the top element of the stack,
Find-Max, which returns (but does not remove) the largest element of the stack, and
Find-Min, which returns (but does not remove) the smallest element of the stack, and


What would be the fastest implementation of this data structure?  How might I go about writing it in Java?
解决方案
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.

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)
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)
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)
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)
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).

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)
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.

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.

Hope this helps!

EDIT: 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）更有效？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！