今天來看一題簡單的 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，整個程式的記憶體用量多了一倍。
這個是典的用空間換取時間的例子。在實務上，在一些效能要求很高的系統中，這是一種很常見的手法來提高系統的效率。如果這個函式常常被使用到的話，這樣的設計或許就很划算。之後再來分享一下這個主題吧。
