题目

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中，调用min、push、pop的时间复杂度都是o（1）。

思路

一开始看到o（1）的时候吓傻了，心理想着肯定需要遍历啊，比较啊，怎么可能是o（1）。但是，要知道，我们可以用空间来换时间啊……

利用一个辅助栈来存放最小值

    栈  3，4，2，5，1     辅助栈 3，3，2，2，1 每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈顶 当出栈时，辅助栈也要出栈 这种做法可以保证辅助栈顶一定都当前栈的最小值

import java.util.Stack; public class Solution { static Stack<Integer> stack=new Stack<Integer>(); static Stack<Integer> minStack=new Stack<Integer>(); public void push(int node) { stack.push(node); if(minStack.size() == 0 || node < minStack.peek()) minStack.push(node); else minStack.push(minStack.peek()); } public void pop() { if(stack.size()>0&&minStack.size()>0){ stack.pop(); minStack.pop(); } } public int top() { if(minStack.size()>0) return minStack.peek(); return -1; } public int min() { if(minStack.size()>0) return minStack.peek(); return -1; } }

注意

要熟悉栈的操作，peek（）是得到栈顶 ，不删除

push中的判断条件minStack.size() == 0 放到 node < minStack.peek()之前，。因为 node < minStack.peek()放到前边的话，minStack中还没有数据的情况下会报错，这时程序就终止了，不会执行下边的minStack.size() == 0