最小栈

leetCode–155(最小栈)

解法一：辅助栈

使用一个辅助栈来存储所扫描元素的最小值。

代码为：

class MinStack {
    //使用辅助栈
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) minStack.push(val);
        //最小栈，每次添加所遍历到的最小值
        else minStack.push(Math.min(val,minStack.peek()));
    }

    public void pop() {
        stack.pop();
        //这一步千万不要忘记，存储最小值的栈也要出栈
        minStack.pop();
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

解法二：不使用额外空间

数组栈，栈中每个元素都是一个数组，数组长度为2，第一个元素是遍历到数的值，第二个元素是所遍历的最小值。

代码为：

class MinStack {
    Stack<int[]> stack;
    public MinStack() {
        stack = new Stack<int[]>();
    }
    
    public void push(int val) {
        if(stack.isEmpty()) stack.push(new int[]{val,val});
        else{
            stack.push(new int[]{val,Math.min(val,stack.peek()[1])});
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek()[0];
    }
    
    public int getMin() {
        return stack.peek()[1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */