设计一个堆栈，这样getMinimum（）应该是O（1） [英] design a stack such that getMinimum( ) should be O(1)
问题描述
这是一个面试问题之一。需要设计一个堆栈持有使得getMinimum（）函数应返回的最少元件在栈的整数值。
例如：考虑下面的例子
情况1 5 - > TOP 1 4 6 2 当getMinimum（）被调用它应该返回1，这是最小元素 在栈。 案例＃2 stack.pop（） stack.pop（） 注：两个5和1 poped出栈。所以在此之后，堆栈 好像， 4 - >顶 6 2 当getMinimum（）被调用是应返回2这是最低的 叠加。
制约性：
- getMinimum应该返回最小值为O（1）
- 在空间的限制也有在设计时就要考虑这一点，如果你使用额外的空间，它应该是恒定的空间。
编辑：这失败的恒空间的限制 - 它基本上一倍所需的空间。我很怀疑，有一个解决方案，它的不的，虽然这样做，没有什么地方冲倒运行的复杂性（例如，使得PUSH / POP为O（n））。注意，这并不会改变所需的空间的复杂性的，例如如果你已经有了一个堆栈为O（n）的空间需求，这仍然将是为O（n），只是用不同的常数因子。
非恒定的空间解决方案
请最低值都在堆栈中低的重复堆栈。当你弹出主堆栈，弹出最小堆了。当你主推栈，无论是推新的元素或最小电流值，以较低者为准。 getMinimum（）然后实现为刚 minStack.peek（）。
因此，使用你的榜样，我们必须：
实时堆栈敏栈
5 - ＆GT; TOP 1
1 1
4 2
6 2
2 2
弹出两次后你会得到：
实时堆栈敏栈
4 2
6 2
2 2
请让我知道这是没有足够的信息。这很简单，当你神交，但它可能需要一点头刮起初：）
（当然，不足之处是它的两倍空间的要求执行时间不显著吃亏，但 - 。也就是说，它的仍然是相同的复杂性）
编辑：有一个变化是稍微繁琐，但具有更好的空间的总称。我们还有该分栈，但我们只从它弹出，当我们从主栈中弹出的值等于一个在最小栈。我们只的推的时被推到主堆栈中的值最小堆栈小于或等于应用于当前的最小值。这允许重复的最小值。 getMinimum（）仍然只是一个偷看操作。例如，以原始版本，并再次推1，我们会得到：
实时堆栈敏栈
1 - ＆GT; TOP 1
5 1
1 2
4
6
2
从上面的持久性有机污染物膨化从两个堆栈，因为1 == 1，离开：
实时堆栈敏栈
5 - ＆GT; TOP 1
1 2
4
6
2
再次爆裂的只有的持久性有机污染物从主堆栈，因为5> 1
实时堆栈敏栈
1 1
4 2
6
2
再次爆裂弹出两个堆栈，因为1 == 1：
实时堆栈敏栈
4 2
6
2
这结束了相同的最坏情况下的空间复杂度（双原栈），但更好的空间使用情况，如果我们很少得到一个新的最小等于。
编辑：这是皮特的邪恶计划的实施。我没有测试它彻底，但我的认为的也没关系：）
使用System.Collections.Generic;
公共类FastMinStack＆LT; T＆GT;
{
私人只读堆栈＆LT; T＆GT;堆栈=新的堆栈＆LT; T＆GT;（）;
//可以把它传递到构造函数
私人只读的IComparer＆LT; T＆GT;比较器=的Comparer＆LT; T＆GT; .DEFAULT;
私人牛逼currentMin;
大众T最低
{
{返回currentMin; }
}
公共无效推送（T元）
{
如果（stack.Count == 0 ||
comparer.Compare（元件，currentMin）所述; = 0）
{
stack.Push（currentMin）;
stack.Push（元）;
currentMin =元;
}
其他
{
stack.Push（元）;
}
}
公共牛逼POP（）
{
牛逼RET = stack.Pop（）;
如果（comparer.Compare（RET，currentMin）== 0）
{
currentMin = stack.Pop（）;
}
返回RET;
}
}
This is one of an interview question. You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.
For example: consider the below example
case #1 5 --> TOP 1 4 6 2 When getMinimum() is called it should return 1, which is the minimum element in the stack. case #2 stack.pop() stack.pop() Note: Both 5 and 1 are poped out of the stack. So after this, the stack looks like, 4 --> TOP 6 2 When getMinimum() is called is should return 2 which is the minimum in the stack.
Constriants:
- getMinimum should return the minimum value in O(1)
- Space constraint also has to be considered while designing it and if you use extra space, it should be of constant space.
EDIT: This fails the "constant space" constraint - it basically doubles the space required. I very much doubt that there's a solution which doesn't do that though, without wrecking the runtime complexity somewhere (e.g. making push/pop O(n)). Note that this doesn't change the complexity of the space required, e.g. if you've got a stack with O(n) space requirements, this will still be O(n) just with a different constant factor.
Non-constant-space solution
Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().
So using your example, we'd have:
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
After popping twice you get:
Real stack Min stack
4 2
6 2
2 2
Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)
(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)
EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
Popping from the above pops from both stacks because 1 == 1, leaving:
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
Popping again only pops from the main stack, because 5 > 1:
Real stack Min stack
1 1
4 2
6
2
Popping again pops both stacks because 1 == 1:
Real stack Min stack
4 2
6
2
This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".
EDIT: Here's an implementation of Pete's evil scheme. I haven't tested it thoroughly, but I think it's okay :)
using System.Collections.Generic;
public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;
private T currentMin;
public T Minimum
{
get { return currentMin; }
}
public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}
public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}
这篇关于设计一个堆栈，这样getMinimum（）应该是O（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
