设计一个堆栈，使得getMinimum( )应该是O(1)
这是一个面试问题。
你需要设计一个包含整数值的堆栈，这样getMinimum()函数就应该返回堆栈中的最小元素。
例如：
案例#1
5个←顶部
1
4.
6
2
当调用getMinimum()时，它应该返回1，这是堆栈中的最小元素。
案例#2
stack.pop()
stack.pop()
注意:5和1都会从堆栈中弹出。因此，在此之后，堆栈看起来像
4个←顶部
6
2
当调用getMinimum()时，它应该返回2，这是堆栈中的最小值。约束：
- getMinimum应返回O(1)中的最小值
- 空间约束在设计时也必须考虑，如果使用额外空间，则应为常量空间。
回答 30
Stack Overflow用户
发布于 2009-03-26 09:34:37
编辑:这不符合“常量空间”的约束-它基本上是所需空间的两倍。我非常怀疑有没有一种解决方案可以做到这一点，而不破坏运行时的复杂性(例如，使推送/弹出O(n))。注意，这不会改变所需空间的复杂性，例如，如果你有一个具有O(n)空间需求的堆栈，这仍然是O(n)，只是具有不同的常数因子。
非常空解
保持一个“复制”堆栈，即“堆栈中所有值的最小值”。当你弹出主堆栈时，也要弹出最小堆栈。当您推送主堆栈时，推送新元素或当前最小值中较低的一个。然后，仅将getMinimum()实现为minStack.peek()。
因此，使用您的示例，我们将拥有：
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2弹出两次后，你会得到：
Real stack Min stack
4 2
6 2
2 2如果这不是足够的信息，请告诉我。摸索起来很简单，但一开始可能会有点摸不着头脑:)
(当然，缺点是它使空间需求翻了一番。执行时间不会受到太大影响--也就是说，它的复杂度仍然是一样的。)
编辑:有一个变种，它稍微有点麻烦，但总体上有更好的空间。我们仍然有最小堆栈，但是只有当我们从主堆栈弹出的值等于最小堆栈上的值时，我们才会从它中弹出。只有当推送到主堆栈上的值小于或等于当前的最小值时，我们才会推送到最小堆栈。这允许重复的最小值。getMinimum()仍然只是一个窥视操作。例如，取原始版本并再次按下1，我们将得到：
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2 从上面的两个堆栈中弹出，因为1 == 1，留下：
Real stack Min stack
5 --> TOP 1
1 2
4
6
2 再次弹出仅从主堆栈弹出，因为5> 1：
Real stack Min stack
1 1
4 2
6
2 再次弹出两个堆栈，因为1 == 1：
Real stack Min stack
4 2
6
2 这最终导致了相同的最坏情况下的空间复杂度(是原始堆栈的两倍)，但如果我们很少获得“新的最小值或相等”，则空间使用率要好得多。
编辑:这是Pete的邪恶计划的实现。我还没有彻底测试过它，但我认为这是可以的:)
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;
}
}Stack Overflow用户
发布于 2009-03-26 09:33:20
添加一个字段来保存最小值，并在Pop()和Push()期间更新它。这样，getMinimum()将是O(1)，但是Pop()和Push()必须做更多的工作。
如果弹出最小值，则Pop()将为O(n)，否则它们都将为O(1)。根据Stack实现，当调整大小时，Push()变为O(n)。
下面是一个快速实现
public sealed class MinStack {
private int MinimumValue;
private readonly Stack<int> Stack = new Stack<int>();
public int GetMinimum() {
if (IsEmpty) {
throw new InvalidOperationException("Stack is empty");
}
return MinimumValue;
}
public int Pop() {
var value = Stack.Pop();
if (value == MinimumValue) {
MinimumValue = Stack.Min();
}
return value;
}
public void Push(int value) {
if (IsEmpty || value < MinimumValue) {
MinimumValue = value;
}
Stack.Push(value);
}
private bool IsEmpty { get { return Stack.Count() == 0; } }
}Stack Overflow用户
发布于 2009-03-26 23:32:28
public class StackWithMin {
int min;
int size;
int[] data = new int[1024];
public void push ( int val ) {
if ( size == 0 ) {
data[size] = val;
min = val;
} else if ( val < min) {
data[size] = 2 * val - min;
min = val;
assert (data[size] < min);
} else {
data[size] = val;
}
++size;
// check size and grow array
}
public int getMin () {
return min;
}
public int pop () {
--size;
int val = data[size];
if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min += min - val;
return prevMin;
} else {
return val;
}
}
public boolean isEmpty () {
return size == 0;
}
public static void main (String...args) {
StackWithMin stack = new StackWithMin();
for ( String arg: args )
stack.push( Integer.parseInt( arg ) );
while ( ! stack.isEmpty() ) {
int min = stack.getMin();
int val = stack.pop();
System.out.println( val + " " + min );
}
System.out.println();
}
}它显式地存储当前的最小值，如果最小值发生变化，它不会推入该值，而是将一个相同差的值推入新的最小值的另一侧(如果min =7，您按下5，它将推入3( 5-|7-5| = 3)，并将min设置为5；如果您在min为5时弹出3，则它会看到弹出的值小于min，因此颠倒该过程，为新的min获取7，然后返回前一个min)。因为任何没有引起改变的值，当前最小值大于当前最小值，你可以用来区分改变最小值的值和不改变最小值的值。
在使用固定大小整数的语言中，您从值的表示中借用了一些空间，因此它可能会下溢，断言将失败。但除此之外，它是恒定的额外空间，所有的操作仍然是O(1)。
相反，基于链表的堆栈还有其他地方可以借鉴，例如，在C中，下一个指针的最低有效位，或在Java中，链表中对象的类型。对于Java来说，这确实意味着与连续堆栈相比，使用了更多的空间，因为每个链接都有对象开销：
public class LinkedStackWithMin {
private static class Link {
final int value;
final Link next;
Link ( int value, Link next ) {
this.value = value;
this.next = next;
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
return value;
}
}
private static class MinLink extends Link {
MinLink ( int value, Link next ) {
super( value, next );
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
int prevMin = stack.min;
stack.min = value;
return prevMin;
}
}
Link top;
int min;
public LinkedStackWithMin () {
}
public void push ( int val ) {
if ( ( top == null ) || ( val < min ) ) {
top = new MinLink(min, top);
min = val;
} else {
top = new Link(val, top);
}
}
public int pop () {
return top.pop(this);
}
public int getMin () {
return min;
}
public boolean isEmpty () {
return top == null;
}在C中，开销是没有的，你可以借用下一个指针的lsb：
typedef struct _stack_link stack_with_min;
typedef struct _stack_link stack_link;
struct _stack_link {
size_t next;
int value;
};
stack_link* get_next ( stack_link* link )
{
return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}
bool is_min ( stack_link* link )
{
return ( link -> next & 1 ) ! = 0;
}
void push ( stack_with_min* stack, int value )
{
stack_link *link = malloc ( sizeof( stack_link ) );
link -> next = ( size_t ) stack -> next;
if ( (stack -> next == 0) || ( value == stack -> value ) ) {
link -> value = stack -> value;
link -> next |= 1; // mark as min
} else {
link -> value = value;
}
stack -> next = link;
}
etc.;然而，这些都不是真正的O(1)。它们在实践中不需要更多的空间，因为它们利用了这些语言中数字、对象或指针表示的漏洞。但使用更紧凑表示的理论机器在每种情况下都需要向该表示添加额外的比特。
https://stackoverflow.com/questions/685060
复制相似问题