[数据结构与算法]Leetcode--Java--155. 最小栈

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

样例描述

思路

辅助栈

1. 由于删除时可能会删除掉当前的最小值，所以用一个变量来存是不行的，得用一个辅助栈来对应同步存储当前栈里元素的最小值。
2. 两个栈同步插入，同步删除，辅助栈就是实时的存最小值的栈

方法二：不借助，用栈存数组元素
将当前所有元素的最小值和当前的值绑定在一起

代码

方法一：

class MinStack {
    Deque<Integer> stack, minStack;
    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }
    
    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();
 */

方法二：

class MinStack {
   //数组元素存储 [当前值， 当前所有元素中的最小值]
    Deque<int[]> stack;
    public MinStack() {
        stack = new LinkedList<>();
    }
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new int[]{val, val});
        } else {
            stack.push(new int[]{val, Math.min(stack.peek()[1], val)});
        }
    }
    
    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();
 */