1. Maintain two stacks: mainStack and minStack 2. push(val): a. Push val onto mainStack b. If minStack is empty OR val <= minStack.top(): push val onto minStack 3. pop(): a. If mainStack.top() == minStack.top(): pop minStack b. Pop mainStack 4. top(): return mainStack.top() 5. getMin(): return minStack.top()
題目描述：設計一個支援 push、pop、top 和 getMin 四種操作的堆疊，其中 getMin 必須在 O(1) 時間內回傳堆疊中的最小值。
解題思路：普通堆疊無法在 O(1) 時間內取得最小值，因為 pop 之後最小值可能改變。解法是使用雙堆疊：一個主堆疊存所有元素，另一個輔助堆疊（minStack）同步追蹤目前的最小值。每次 push 時，若新元素小於等於 minStack 頂端（或 minStack 為空），則同時推入 minStack；每次 pop 時，若被移除的元素等於 minStack 頂端，則同步從 minStack 彈出。如此 getMin 只需回傳 minStack 的頂端即可。
時間複雜度：O(1) — push、pop、top、getMin 全部為常數時間操作。
空間複雜度：O(n) — 最壞情況下（元素持續遞減）minStack 儲存與主堆疊等量的元素。
單堆疊儲存差值 O(1) 空間：堆疊每個位置不存實際值，而是存「當前值與目前最小值的差」，並用一個外部變數追蹤最小值。省去額外堆疊，但數值需用 long long 避免溢位，實作較複雜。
每個節點附帶最小值 O(n)：自訂鏈結串列節點，每個節點除了存值之外也存入節點當下的最小值。邏輯清晰，但每個節點多存一個整數。
getMax 也在 O(1) 時間內完成？push 的值有大量重複，如何減少 minStack 佔用的空間？