剑指Offer 21 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数

思路

不考虑时间复杂度的话，直接通过Iterator 找到栈的最小值；

如果考虑时间复杂度的话，就引入辅助栈，用于当前栈的最小值

Stack<Integer> stack = new Stack<>();
public void push(int node) {
            stack.push(node);
}
public void pop() {
    stack.pop();
}
public int top() {
       return stack.peek();
}
public int min() {
        int min = stack.peek();
        int temp = 0;
    Iterator<Integer> iterator = stack.iterator();
    while (iterator.hasNext())
    {
        temp=iterator.next();
        if (temp<min)
            min=temp;
    }
    return  min;
}

Stack<Integer> stack = new Stack<>();
   Stack<Integer> min = new Stack<>();
   public void push(int node) {
       stack.push(node);
       if (min.size()==0||node<min.peek())
           min.push(node);
       else
           min.push(min.peek());
   }
   public void pop() {
       stack.pop();
       min.pop();
   }
   public int top() {
       return stack.peek();
   }
   public int min() {
       assert (stack.size()>0&&min.size()>0);
     return min.peek();
   }

收获

辅助栈的引入真的很神奇，通过空间复杂度代替了时间复杂度；

2017-03-25