# Min Stack ### Source - lintcode: [(12) Min Stack](http://www.lintcode.com/en/problem/min-stack/) ~~~ Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1 Note min operation will never be called if there is no number in the stack ~~~ ### 題解 『最小』棧，要求在棧的基礎上實現可以在 O(1)O(1)O(1) 的時間內找出最小值，一般這種 O(1)O(1)O(1)的實現往往就是哈希表或者哈希表的變體，這里簡單起見可以另外克隆一個棧用以跟蹤當前棧的最小值。 ### Java ~~~ public class Solution { public Solution() { stack1 = new Stack<Integer>(); stack2 = new Stack<Integer>(); } public void push(int number) { stack1.push(number); if (stack2.empty()) { stack2.push(number); } else { stack2.push(Math.min(number, stack2.peek())); } } public int pop() { stack2.pop(); return stack1.pop(); } public int min() { return stack2.peek(); } private Stack<Integer> stack1; // original stack private Stack<Integer> stack2; // min stack } ~~~ ### 源碼分析 取最小棧的棧頂值時需要先判斷是否為空棧(而不僅是 null)。 ### 復雜度分析 均為 O(1)O(1)O(1).