3

インターネットでアルゴリズムに関する質問を見つけました。

関数を含むスタックを定義します。これにより、スタック内の最小数を取得でき、、およびの時間複雑度はすべてO(1)です。minminpoppushmin

の複雑さはO(1)であることは知っpopていますが、毎回最小数を記憶するように変数を定義すると、複雑さをどのように作成するかわかりませんが、 の場合、最小数は変わる可能性があるので、そうする必要があります2 番目に小さい数を見つけます。これは、複雑さがO(1)にならないことを意味します。pushminO(1)pushpoppop

では、要件を満たすためにスタックをどのように定義すればよいでしょうか?

4

3 に答える 3

5

最小値を持つ別のスタックを用意してください。通常のスタックに値をプッシュするときは、最小スタックに値をプッシュします。通常のスタックから値をポップするときは、最小スタックから値をポップします。最小スタックにプッシュする値は、現在の最小スタック トップと新しい値の最小値になります。

Python での実装例を次に示します。

class MinStack:
  def __init__(self):
    self.values = []
    self.minimums = []

  def push(self,value):
    self.values.append(value)
    if len(self.minimums)==0:
      self.minimums.append(value)
    else:
      self.minimums.append(min(self.min(),value))

  def pop(self):
    self.minimums.pop()
    return self.values.pop()

  def min(self):
    return self.minimums[-1]
于 2013-07-17T03:39:09.387 に答える
0

push値をing している間、最小値をスタック変数に保持できます。pushed 値が次の値より大きい場合は、変数を現在の値にpush設定します。minpush

例えば：

class _stack {
   int minValue;
   struct stackBucket{
      int data;
   }
   ....
   void push(int lastData){
       //push to the stack
       if(lastData < minValue) {
          minValue = lastData;
       }
  }
  int min(){ return minValue;}
};
于 2013-07-17T03:43:44.610 に答える