LeetCode 155. Min Stack & 剑指Offer 30. 包含 min 函数的栈 [Easy]

带取最小值功能的栈。

题目来源：https://leetcode.com/problems/min-stack

题目难度：Easy

解答1：

核心思想

使用两个栈，一个数据栈，一个最小值栈。push 的时候，如果小于等于当前最小值，同时压入两个栈，然后每次弹出的时候，数据栈弹出的数和最小值栈的栈顶作比较，如果相同，那么把最小值也弹出。

代码

import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
    private Deque<Integer> stackData;
    private Deque<Integer> stackMin;

    /** initialize your data structure here. */
    public MinStack() {
        this.stackData = new ArrayDeque<>();
        this.stackMin = new ArrayDeque<>();
    }

    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum <= this.getMin()) {
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        int value = this.stackData.pop();
        if (value == this.getMin()) {
            this.stackMin.pop();
        }
        return value;
    }

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

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}

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

解答2[Java]：

核心思路

同样使用两个栈，不过压入逻辑相比解答1修改了一下。当要入栈的数字小于当前最小值的时候，把入栈的数字同时压入数据栈和最小值栈。当要入栈的数字大于等于当前最小值的时候，把当前最小值取出来再压入最小值栈一次，相当于当前的最小值是冗余的，但是冗余自有冗余的用处。

弹出元素的时候，不需要再进行检查，弹出元素的同时，也把最小值栈的元素弹出，因为最小值栈的元素是冗余的，就是为了一一对应，不用再检查。

代码

import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
    private Deque<Integer> stackData;
    private Deque<Integer> stackMin;

    /** initialize your data structure here. */
    public MinStack() {
        this.stackData = new ArrayDeque<>();
        this.stackMin = new ArrayDeque<>();
    }

    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum < this.getMin()) {
            this.stackMin.push(newNum);
        } else {
            int newMin = this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }

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

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}

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