题目

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

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

定义方法

我们先把栈所需要的方法定义好，接下来我们采用数组去实现栈

class MinStack {

    public MinStack() {

    }
    
    public void push(int val) {

    }
    
    public void pop() {

    }
    
    public int top() {

    }
    
    public int getMin() {

    }
}

初始化

用两个数组表示两个栈，设置两个变量代表栈顶，dataStack表示元素栈用来存放用户随意添加的值，minStack表示辅助栈把用户在dataStack里面的最小值添加到minStack

class MinStack {
    private Integer[] dataStack;     // 元素栈
    private Integer[] minStack;     // 最小值栈
    private int top; 				// 栈顶
    private int min;

    public MinStack() {
        dataStack = new Integer[10];
        minStack = new Integer[10];
        top = -1;
        min = -1;  
    }
    ....
}

实现push方法

实现push方法，具体步骤

1. 将值添加到dataStack，并top++表示dataStack栈顶+1
2. 判断minStack是否是第一次，是第一次直接把dataStack的值添加到minStack。或者判断minStack是否大于添加元素，如果大于则添加到minStack中并min++表示栈顶+1
3. 判断dataStack和minStack是否栈满如果栈满则进行扩容

具体代码如下

public void push(int val) {
    if(top >= dataStack.length - 1) {
        dataStack = Arrays.copyOf(dataStack, top * 2);
    }
    dataStack[++top] = val;

    if(min >= minStack.length - 1) {
        minStack = Arrays.copyOf(minStack, top * 2);
    }
        
    if(min < 0 || minStack[min] > val) {
        minStack[++min] = val;
    }
}

实现pop方法

实现pop只需要把控制栈顶变量进行减一即可,如果考虑到减一之后原有地址元素没有被改变可采用第二种方法
方法一：

public void pop() {
    if (min <= 0 || top <= 0) {
        throw new RuntimeException("栈空了,还pop,cnm");
    }
    System.out.println("minStack = " + dataStack[top--]);
    System.out.println("minStack = " + minStack[min--]);
}

方法二:

public void pop() {
    if (min <= 0 || top <= 0) {
        throw new RuntimeException("栈空了,还pop,cnm");
    }
    dataStack[top--] = null;
    minStack[min--] = null;
}

实现top方法

判断栈顶top是否大于-1，如果不大于说明栈空了

    public int top() {
        return top > -1 ? dataStack[top] : null;
    }

实现getMin方法

我们只需要把minStack进行出栈就知道最小值了

    public int getMin() {
        if (min <= 0) {
            throw new RuntimeException("栈空了");
        }
        return minStack[min];
    }

完整代码如下

public class MinStack {
    private Integer[] dataStack;
    private Integer[] minStack;
    private int top;
    private int min;


    public MinStack() {
        dataStack = new Integer[10];
        minStack = new Integer[10];
        top = 0;
        min = 0;
    }

    public void push(int val) {
        if (top >= dataStack.length - 1) {
            dataStack = Arrays.copyOf(dataStack, top * 2);
        }
        dataStack[top++] = val;

        if (min >= minStack.length - 1) {
            minStack = Arrays.copyOf(minStack, top * 2);
        }

        if (min == 0 || minStack[min] > val) {
            minStack[min++] = val;
        }
    }

    public void pop() {
        if (min <= 0 || top <= 0) {
            throw new RuntimeException("栈空了,还pop");
        }
        dataStack[top--] = null;
        System.out.println("minStack = " + dataStack[top--]);
        System.out.println("minStack = " + minStack[min--]);
    }

    public int top() {
        return top > -1 ? dataStack[top] : null;
    }

    public int getMin() {
        if (min <= 0) {
            throw new RuntimeException("栈空了");
        }
        return minStack[min];
    }
}

进行测试

定一个测试类进行测试

public class MinStackTest {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(1);
        minStack.push(2);
        minStack.push(-3);
        minStack.push(-3);
        minStack.push(-3);
        minStack.push(-3);
        minStack.push(-3);
        minStack.push(-100);
        minStack.push(-100);
        minStack.push(-100);
        minStack.push(-100);
        minStack.push(1000);
        minStack.pop();
        minStack.pop();
        System.out.println("minStack.top() = " + minStack.top());
        minStack.pop();
        minStack.pop();
        minStack.pop();
        System.out.println("minStack" + minStack.getMin());
    }
}

测试结果:

符合题目