题目

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的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 stack=new Stack();

static Stack minStack=new Stack();

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