1 題目描述

這題的重點在於要實現一個可以取得最小值的 stack，並且要求時間複雜度為 O(1)。解題思路的重點是，你要怎麼確保在 push() 的時候，更新最小值，並且在 pop() 的時候，如果 pop() 出當前最小值時，也要更新最小值。

2 解法

2.1 我的解法

有沒有發現重點，當 pop() 和 push() 的時候，最小值也會有所更新，在 pop() 的時候，最小的值被剔除時，我們希望取得第二小，因此我們會需要一個 min_stack 來記錄當前最小值，如果遇到當前更小的，就 push() 進去 min_stack 裡面。這樣儘管最小的被 pop() 出去，我們仍然可以取得第二小的值。

大概是這種感覺：

每當 push 新的值進去時，都要與 min_stack[-1] 最小值比較是否更小，若更小，也要 push 進去 min_stack 裡面。

每當 pop 出去時，也要檢查 pop 出去的值是否是當前的最小值，若是，也要把當前的 min_stack[-1] pop 出去

其他的功能就跟 stack 一樣，在 python 可以使用 list 來實現 stack 的功能。 top() 可以使用 list[-1] 的方式取得，他仍然時間複雜度是 O(1)。下面註解的地方是我原本寫的，但是經過參考別人的後發現有更簡潔的寫法，所以我就改成更簡潔的寫法，註解可以參考。

class MinStack:

    def __init__(self):
        self.min_stack: List[int] = []
        self.stack: List[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        # 原本
        # if not self.min_stack:
        #     min_data = self.min_stack[-1]
        #     if min_data >= val:
        #         self.min_stack.append(val)
        # else:
        #     self.min_stack.append(val)

        # 可以精簡成這樣
        # 如果 min_stack 是空的，或是 val 比 min_stack[-1] 還小，就 push 進去 min_stack 裡面
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    # 關鍵在 pop 掉 min 怎麼確保找到 第二小的 min
    def pop(self) -> None:
        # 原本寫法
        # data = self.stack.pop()
        # if self.min_stack[-1] == data:
        #     self.min_stack.pop()

        # 不需要浪費記憶體 data
        # 如果發現 pop 出去的值是最小值，也要 pop 出去 min_stack 裡面
        if self.stack[-1] == self.minStack[-1]:
            self.minStack.pop()
        self.stack.pop()

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

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

時間複雜度O(1) push(), pop(), top(), getMin() 操作的時間複雜度均為 O(1)。
空間複雜度O(n) 由於 min_stack 和 stack 存儲 n 個不同的數字，因此空間複雜度為 O(n)。

2.2 其他方法

還有一種方法，可以讓程式碼更簡潔，但是空間複雜度方便可能會比第一個方法更大，那就是在 push() 的時候，不管是不是最小值，都要 push 進去 min_stack 裡面，只是 push 進去的必須是當前的最小值，這樣在 pop() 的時候，就不用檢查是否是最小值，直接 pop 出去就好。這樣的好處是程式碼更簡潔，但是空間複雜度可能會比較大，因為 min_stack 裡面會有很多重複的值。

大概是這種感覺：

class MinStack2:

    def __init__(self):
        # 如果必須 getMin 是 O(1) 那只能有另一個 stack 維護 min 這樣 pop 出來某個還可以繼續往下 pop
        self.min_stack: List[int] = []
        self.stack: List[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.min_stack:
            val = min(self.min_stack[-1], val)
        # 整個的精華重點在這裡
        self.min_stack.append(val)

    # 然後你會發現 pop() 的實作變得非常簡單 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

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

我們仔細看一下這兩個方法的差異：

# 第一種方法
    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            # 只有在遇到更小的值，才 push 進去 min_stack 裡面
            self.min_stack.append(val)
# 第二種方法
    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.min_stack:
            # 先比較當前的 min_stack[-1] 和 val 誰比較小
            val = min(self.min_stack[-1], val)
        # "每次" 都塞入當前的最小值
        self.min_stack.append(val)


# 第一種方法
    def pop(self) -> None:
        # 每次還要檢查pop出去的值是否是最小值
        if self.stack[-1] == self.minStack[-1]:
            self.minStack.pop()
        self.stack.pop()
# 第二種方法
    def pop(self) -> None:
        # 無腦 pop 出去就好
        self.stack.pop()
        self.min_stack.pop()

時間複雜度O(1) push(), pop(), top(), getMin() 操作的時間複雜度均為 O(1)。
空間複雜度O(n) 由於 min_stack 和 stack 存儲 n 個不同的數字，因此空間複雜度為 O(n)。

3 總結

今天偷看了一下，一開始想不透到底要怎麼用 O(1) 的時間複雜度就可以做到 pop() 後仍然保持最小值，一開始都是用一個變數儲存最小值，但是沒想到這題的精髓在使用 stack 紀錄最小值，這樣在 pop() 的時候，也可以保持最小值。自己不應該每次看到 O(1) 就要無腦想用 Hash Table，這是無序的狀態下搜尋某個關鍵字使用，但是這題是有序的，所以使用 stack 來記錄最小值是一個很好的方法。