Leetcode 155. Min Stack -

Min Stack : 設計一個棧，可以實作push、pop、top，並在常數時間內獲取最小元素的堆疊。

Python

建立一個 list min_stack紀錄堆疊最小值
建立stack list 作為堆疊紀錄
push：把值放進堆疊後面，如果該值小於等於 min_stack 堆疊的最後一筆資料，則一併加入 min_stack 堆疊
pop：從 stack 移除最上面一筆值，如果該值等於 min_stack 最後一筆，一併從堆疊移除
top：取得堆疊最上面一個元素stack[-1]
getMin：取得最小值，也就是 min_stack 的最後一個元素min_stack[-1]

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Python

相關