题解 | #设计getMin功能的栈#

import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public Stack<Integer> stackData;
    public Stack<Integer> stackMin;

    public Main() {
        this.stackData = new Stack();
        this.stackMin = new Stack();
    }

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

    //pop
    public int pop() {
        if (stackData.isEmpty()) {
            return 0;
        }
        int res = stackData.pop();
        if(res == stackMin.peek()) {
            stackMin.pop();
        }
        return res;
    }

    //getMin
    public int getMin() {
        if(stackMin.isEmpty()) {
            return 0;
        }else {
            return stackMin.peek();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main main = new Main();
        int n = scanner.nextInt();

        for(int i = 0; i < n; i++) {
            String op = scanner.next();
            if("push".equals(op)) {
                int num = scanner.nextInt();
                main.push(num);
            }else if("getMin".equals(op)) {
                System.out.println(main.getMin());
            }else{
                main.pop();
            }
        }
    }
}

代码思路:

在设计时，我们使用两个栈，一个用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。

（1）压入数据规则

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：

• 如果为空，则newNum也压入stackMin。
• 如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
• 如果newNum更小或两者相等，则newNum也压入stackMin；
• 如果stackMin中栈顶元素小，则stackMin不压入任何内容。

（2）弹出数据规则

先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。

通过上文提到的压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈中的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。

当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value。

（3）查询当前栈中的最小值元素操作

由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值。所以，stackMin的栈顶元素始终是当前stackData中的最小值。