# LeetCode Easy 155. Min Stack

tags: leetcode

問題

• Explore
• Problems

アイデア

｢push，pop，top，getMinというメソッドをサポートするスタックを実装せよ｣という問題です．ただし，getMinの時間計算量は定数時間です．

実装するだけです．

解法

stackに(x， <xが出るまでの最小値)を保存する．コレに対して，stackを実行する

計算量

• 時間計算量
  • 初期化
    • $O(1)$
  • push
    • $O(1)$
  • pop
    • $O(1)$
  • top
    • $O(1)$
  • getMin
    • $O(1)$
• 空間計算量
  • 初期化
    • $O(1)$
  • push
    • $O(n)$
  • pop
    • $O(1)$
  • top
    • $O(1)$
  • getMin
    • $O(1)$

Python

class MinStack:

    def __init__(self):
        self.stack = []
        
    def push(self, x):
        self.stack.append((x, min(self.getMin(), x))) 
           
    def pop(self):
        self.stack.pop()

    def top(self):
        if self.stack:
            return self.stack[-1][0]
        
    def getMin(self):
        if self.stack:
            return self.stack[-1][1]
        return sys.maxsize          


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()