LeetCode 155：最小棧 Min Stack

設計一個支持 push，pop，top 操作，並能在常數時間內檢索到最小元素的棧。

• push(x) -- 將元素 x 推入棧中。
• pop() -- 刪除棧頂的元素。
• top() -- 獲取棧頂元素。
• getMin() -- 檢索棧中的最小元素。

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.

示例:

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

解題思路：

起初我以為定義一個指針指向最小值即可，後面才想到在棧中彈出元素時，如果彈出的元素是最小值，那這個指針就需要更 改選擇另一個最小元素。沒辦法，想做到入棧出棧和彈出最小值均為 O(1) 的時間複雜度，那麼只能犧牲空間來換。可以另外新建一個棧來順序存入數據最小值。

注意：Python中沒有單獨的 Stack 數據結構，其實它的數組就有彈出和壓入功能。也可以用 collections.deque() 數據結構。 另外在數據入棧時需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應該將它加入輔助棧。並且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會溢出。

事實上每次都要調用函數判斷是否為空這個操作，相對這道題的運行時間來說很耗時，就這道題而言是可以避免的，只需給輔助棧加入整型最大值作為棧底元素即可。

Java：

class MinStack {
 Stack<Integer> s1 = new Stack<>();//初始化棧
 Stack<Integer> s2 = new Stack<>();//輔助棧順序存入最小值
 public MinStack() {
 s2.push(Integer.MAX_VALUE);//先加入整型最大值在棧底，避免判斷輔助棧是否為空
 }
 public void push(int x) {
 s1.push(x);
 if (s2.peek() >= x) s2.push(x);//比棧頂元素值小或相等就加入輔助棧
 }
 public void pop() {
 int tmp = s1.pop();
 if (tmp == s2.peek()) s2.pop();//彈出棧的元素值如果和輔助棧頂元素值相等，也在輔助棧彈出它
 }
 public int top() {
 return s1.peek();//返回棧頂元素
 }
 public int getMin() {
 return s2.peek();//返回輔助棧棧頂元素即是最小值
 }
}

Python3：

class MinStack:
 #初始化數據結構(數組)，s2作為輔助棧加入整形最大值做棧底，避免判斷輔助棧是否為空
 def __init__(self):
 self.s1 = []
 self.s2 = []
 self.s2.append(sys.maxsize)
 def push(self, x: int) -> None:
 self.s1.append(x)
 #取棧頂元素直接用數組負值索引 Array[-1] 取最後一個值
 if self.s2[-1] >= x: self.s2.append(x)
 def pop(self) -> None:
 tmp = self.s1.pop()
 if tmp == self.s2[-1]: self.s2.pop()
 def top(self) -> int:
 return self.s1[-1]
 def getMin(self) -> int:
 return self.s2[-1]