Leetcode 筆記 - Min Stack

今天來看一題簡單的 leetcode，雖然說簡單，不過其中解題的思維，也可以應用在很多的系統設計上面。

題目: Min Stack

原始題目如下:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

簡單說就是要實作一個 stack 但是可以支援找到當前 stack 中最小值的功能。
因為基本的 stack 的實作可以直接使用 Array，所以剩下的就是提供找到 Array 中最小值的功能。
有些程式語言有提供回傳 Array 中最小值的功能，可以直接使用。

解法 1 (Python 3)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

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

    def pop(self) -> None:
        self.stack.pop()

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

    def getMin(self) -> int:
        return min(self.stack)

# 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()

上面這個解法很直觀的使用 python list 內建的 append, pop 函式來實作 stack。
至於 getMin 的實作是使用內建的 min 函式。
要注意的是 min 函式的時間複雜度是 O(n)，基本上如果沒有先經過特殊處理(如: 排序)，在 array 中尋找最小元素的時間複雜度都是 O(n)。

解法 2 (Python 3)

那我們有辦法加快速度嗎?
這時候我們可以把 stack 中各種元素的存在的情況視為一種狀態 (state)，然後把各種狀態的最小元素直接存下來。

例如當 stack 是 [3] 的時候最小元素是 3。
當再 push 2 到 stack 中，stack 是 [3, 2] 的時候最小元素是 2。
當再 push 3 到 stack 中，stack 是 [3, 2, 3] 的時候最小元素是 2。
所以我們可以把 stack 在各個不同狀態的最小元素值，以上面的例子來說，分別是 3, 2, 2，存起來，當呼叫 getMin 的時候直接回傳。

因為 stack 在不同長度時會對應到不同的狀態，所以我們會需要使用一個和 stack 一樣長度的 Array 來儲存這些不同狀態的最小值。這個 Array 的長度會和 stack 長度一起變化。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_states = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_states.append(min(x, self.min_states[-1]) if self.min_states else x)

    def pop(self) -> None:
        self.stack.pop()
        self.min_states.pop()

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

    def getMin(self) -> int:
        return self.min_states[-1]  # 直接回傳當前 stack (某個 state) 的最小元素

# 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()

經過這樣的修改，getMin 函式的時間複雜度變成 O(1)。不過要注意的是因為需要多儲存一個不同狀態最小值的 list，整個程式的記憶體用量多了一倍。

這個是典的用空間換取時間的例子。在實務上，在一些效能要求很高的系統中，這是一種很常見的手法來提高系統的效率。如果這個函式常常被使用到的話，這樣的設計或許就很划算。之後再來分享一下這個主題吧。