《剑指Offer》Java刷题 NO.20 包含min函数的栈

《剑指Offer》Java刷题 NO.20 包含min函数的栈(辅助栈空间)

时间：2020-02-28 题目： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路： 既然题目import了Stack，那就是说可以用咯~哈哈哈 因为要保证时间复杂度为O(1),那么只能在空间上做文章了，利用一个辅助栈B用来存当前栈的最小值

压栈时，如果new>B的栈顶元素,A压栈，B不动；如果new<=B的栈顶元素,A压栈，B也压栈 出栈时，如果A的栈顶元素==B的栈顶元素，A出栈，B出栈，更新当前min值为B出栈之后的栈顶元素；否则，A出栈 一定要注意压栈时如果新元素==B的栈顶元素(也就是最小值)时，一定要压栈，相当于在计数(因为可能会出现多次间隔压入同一个最小值的现象)，这样才能保证B的栈顶元素一直是最小值 另外还看到有人用两个ArrayList来代替Stack实现了想要的功能，就不做展示了

Java代码：

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
 * 注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。
 */
import java.util.Stack;
public class MyStack {
          
   
    Stack<Integer> stack=new Stack<>();
    Stack<Integer> minStack=new Stack<>();
    int min=Integer.MAX_VALUE;
    public void push(int node) {
          
   
        if(node<=min)
            minStack.push(node);
        min=minStack.peek();
        stack.push(node);
    }

    public void pop() {
          
   
        if(stack.peek()==minStack.peek())
            minStack.pop();
        stack.pop();
        min=minStack.peek();
    }

    public int top() {
          
   
        return stack.peek();
    }

    public int min() {
          
   
        return min;
    }
}