最小栈

题目信息

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

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

解题思路

每一次的元素弹出都会影响当前最小值的结果，所以采用以下方式来记录

1. 创建辅助栈，存储最小值
2. 创建辅助变量，存储最小值

代码

class MinStack {
    Stack<Integer> minStack = new Stack();
    Stack<Integer> normalStack = new Stack();

    /** initialize your data structure here. */
    public MinStack() {
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        normalStack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }
    
    public void pop() {
        normalStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return normalStack.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 {
    public Stack<Node> stack = new Stack();

    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new Node(val, val));
        } else {
            stack.push(new Node(val, Math.min(val, stack.peek().min)));
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek().value;
    }
    
    public int getMin() {
        return stack.peek().min;
    }

    public static class Node {
        public int value;
        public int min;

        public Node(int value, int min) {
            this.value = value;
            this.min = min;
        }
    }
}

/**
 * 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();
 */

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/min-stack

商业转载请联系官方授权，非商业转载请注明出处。