Pythonの最小スタック

ここでは、一定時間で最小要素をプッシュ、ポップ、トップ、および取得できるスタックを作成する方法を説明します。したがって、関数はpush（x）、pop（）、top（）、getMin（）

これを解決するには、次の手順に従います-

• スタックを最小要素で無限大として初期化します
• プッシュ操作の場合push（x）
  • x
  • xをスタックにプッシュします
• ポップ操作の場合pop（）
  • t：=最上位の要素
  • スタックからtを削除
  • tがminの場合、min：=スタックの最上位要素
• トップ操作の場合top（）
  • 一番上の要素を返すだけです
• getMin操作の場合getMin（）
  • 最小要素を返す

例

理解を深めるために、次の実装を見てみましょう-

class MinStack(object):
   min=float('inf')
   def __init__(self):
      self.min=float('inf')
      self.stack = []
   def push(self, x):
      if x<=self.min:
         self.stack.append(self.min)
         self.min = x
      self.stack.append(x)
   def pop(self):
      t = self.stack[-1]
      self.stack.pop()
      if self.min == t:
         self.min = self.stack[-1]
         self.stack.pop()
   def top(self):
      return self.stack[-1]
   def getMin(self):
      return self.min
m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

入力

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

出力

-3
0
-2