スタックからの最小値

Question

私はいくつかの整数データを含むスタックを持っています。私は、O（1）時間でスタックから最小値を探したい。何か案が？

PS：スタック内のデータの順序付け（増加/減少）がありません。

おかげで、定義によって

Answer 1

2つのスタックを使用してください。 1つはデータ、1つは最小値です。データスタックを押すと、新しい最小値を最小値スタックにプッシュします（新しい最小値は押しているアイテムの最小値で、現在は最小値スタックの最上部にある値です）。ポップアップすると、ポップオフします両方のスタックの（2つのスタックが常に同じ数の要素を持つように）最小要素を見つけるには、最小スタックの最上部を見てください。

min値をポップし、発見、プッシュは、O（1）です。

Answer 2

スタック

のNaveenは、push/pop（LIFO）データ構造です。 1つのスタックを使用することはできません！

Answer 3

O（n）がある最高のあなたつもり行う - あなたが値のそれぞれをチェックし、それらがアグリゲータ最小限に比較する必要があるだろう、そうでない場合はどのようにあなたが最も低くなった知っているだろうか？

値が追加されるときに最小値を保存することができます。これにより、プッシュはO（1）読み取り（事前計算された最小値）の利益のために高価になりますが、それだけです。

Answer 4

私は、なぜこれを一定の時間内に任意の長さで行うと思うのか分かりません。 O（n）

Answer 5

あなたはいつも以上の要素をポップにしたい場合は、おそらくpriority heapのいくつかの種類をお勧めします。最後に押されたものをポップしたいが、スタックに残っている要素の順序を知ることができるようにするには、何らかの種類の検索ツリー。 red-blackは任意の位置から要素の削除をサポートします（あなたのスタックはツリーノードへのポインタを持っていますので、ポップアップするとそれを見つけることができます）。

あなたが唯一の最小（または最大）を知る必要がある場合には、スタックに残って、その後ESRogsは最適です。ここで

Answer 6

はスタックとしてリストを使用してESRogsアルゴリズムのPython実装である：ここで

class ConstantStack: 
    def __init__(self): 
     self.stack = [] 
     self.min_stack = [] 
    def push(self,item): 
     self.stack.append(item) 
     if len(self.min_stack) == 0: 
      self.min_stack.append(item) 
      return 
     # Get the smaller item between the pushed item and the top of the stack 
     smallest = min(item,self.min_stack[-1]) 
     self.min_stack.append(smallest) 
    def pop(self): 
     self.min_stack.pop() 
     return self.stack.pop() 
    def min(self): 
     # NOTE: min_stack[-1] is equivalent to peek() 
     return self.min_stack[-1] 

は、その使用方法の一例である：上純粋に依存して定義することにより、スタック内の

>>> s = ConstantStack() 
>>> s.push(3) 
>>> s.push(7) 
>>> s.push(6) 
>>> s.push(1) 
>>> s.min() 
1 
>>> s.pop() 
1 
>>> # Now that 1 is gone, 3 is the next smallest 
>>> s.min() 
3 
>>> s.pop() 
6 
>>> # 6 was popped but 3 still remains the smallest 
>>> s.min() 
3 
>>> s.pop() 
7 
>>> s.min() 
3 
>>> s.pop() 
3 

Answer 7

#define STACKSIZE 50 

typedef struct stack 
{ 
    int item[STACKSIZE]; 
    int top; 
}MULSTACKEX; 

void InitStack(MULSTACKEX &st) 
{ 
    st.item[STACKSIZE] = 0; 
    st.top = -1; 
} 

void Push(MULSTACKEX &st1, MULSTACKEX &st2, int elem) 
{ 
    if(st1.top == -1) 
    { 
     st1.top++; 
     st1.item[st1.top] = elem; 

     st2.top++; 
     st2.item[st2.top] = elem; 
    } 
    else 
    { 
     st1.top++; 
     st1.item[st1.top] = elem; 

     if(elem < st2.item[st2.top]) 
     { 
      st2.top++; 
      st2.item[st2.top] = elem; 
     } 
    } 
} 

void Display(MULSTACKEX &st1, MULSTACKEX &st2) 
{ 
    cout<<"stack1 elements: "<<endl; 
    for(int i = 0; i <= st1.top; i++) 
    { 
     cout<<st1.item[i]<<"->"; 
    } 

    cout<<endl; 
    cout<<"stack2 elements: "<<endl; 
    for(int i = 0; i <= st2.top; i++) 
    { 
     cout<<st2.item[i]<<"->"; 
    } 

} 

int Pop(MULSTACKEX &st1, MULSTACKEX &st2) 
{ 
    int elem = 0; 
    if(st1.item[st1.top] == st2.item[st2.top]) 
    { 
     elem = st2.item[st2.top]; 
     st2.top--; 

     elem = st1.item[st1.top]; 
     st1.top--; 
    } 
    else 
    { 
     elem = st1.item[st1.top]; 
     st1.top--; 
    } 

    return elem;  
} 
int FindMin(MULSTACKEX &st2) 
{ 
    int elem = st2.item[st2.top]; 
    return elem; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    MULSTACKEX stack1, stack2; 

    InitStack(stack1); 
    InitStack(stack2); 


    Push(stack1,stack2,13); 
    Push(stack1,stack2,17); 
    Push(stack1,stack2,5); 
    Display(stack1,stack2); 

    int min_elem1 = FindMin(stack2); 
    cout<<"Min element in the list is: "<<min_elem1<<endl<<endl; 

    int deletedelem2 = Pop(stack1,stack2); 
    cout<<"Pop element from the stack:"<< deletedelem2 <<endl<<endl; 
    Display(stack1,stack2); 

    cout<<endl<<endl; 

    Push(stack1,stack2,19); 
    Push(stack1,stack2,8); 
    Display(stack1,stack2); 

    cout<<endl<<endl; 

    int deletedelem1 = Pop(stack1,stack2); 
    cout<<"Pop element from the stack:"<< deletedelem1 <<endl<<endl; 
    Display(stack1,stack2); 

    int min_elem2 = FindMin(stack2); 
    cout<<"Min element in the list is: "<<min_elem2<<endl<<endl; 

    return 0; 
}