包含 min 函数的栈

题目要求：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push、pop 的时间复杂度都是 O ( 1 ).

思路：

1. 把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)存到辅助栈 mins 中

代码实现：

public class StackWithMin {

    // 数据栈
    private List<Integer> data = new ArrayList<>();

    // 辅助最小值栈
    private List<Integer> mins = new ArrayList<>();

    /**
     * 思路 1 ：把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)存到辅助栈 mins 中
     *
     *  时间复杂度：O (1)
     *  空间复杂度：O (n)
     */
    private void push1(int num) throws Exception {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(num);
        } else {
            // 辅助栈mins每次push当前data中的最小值
            int min = getMin1();
            if (num >= min) {
                mins.add(min);
            } else {
                mins.add(num);
            }
            System.out.print("push1完后mins栈中的值为：");
            for (int index : mins) {
                System.out.print(index + " ");
            }
        }
    }

    private int pop1() throws Exception {
        // 栈空，异常，返回-1
        if(data.size() == 0) {
            throw new Exception("Stack is Empty!");
        }
        // pop时两栈同步pop
        mins.remove(mins.size() - 1);
        System.out.print("pop1完后mins栈中的值为：");
        for (int index : mins) {
            System.out.print(index + " ");
        }
        return data.remove(data.size() - 1);
    }

    private int getMin1() throws Exception {
        // 栈空，异常，返回-1
        if(mins.size() == 0) {
            throw new Exception("Stack is Empty!");
        }
        // 返回mins栈顶元素
        return mins.get(mins.size() - 1);
    }
}

测试代码：

 @Test
    public void testStackWithMin() throws Exception {
        StackWithMin stackWithMin1 = new StackWithMin();

        /* 思路 1 */
        stackWithMin1.push1(6);
        stackWithMin1.push1(2);
        stackWithMin1.push1(2);

        System.out.println();
        int pop1 = stackWithMin1.pop1();
        System.out.print("data 栈中pop1的元素：" + pop1);
        System.out.println();
        int min1 = stackWithMin1.getMin1();
        System.out.print("data 栈中getMin1为：" + min1);
    }

2. 把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)的索引存到辅助栈 mins 中，每次在data栈中 getMin 的时候比较其索引值与 mins 中存的索引值是否相等，是则出栈。

public class StackWithMin {

    // 数据栈
    private List<Integer> data = new ArrayList<>();

    // 辅助最小值栈
    private List<Integer> mins = new ArrayList<>();

    /**
     * 思路 2 ：把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)的索引存到辅助栈 mins 中，
     * 每次在data栈中 getMin 的时候比较其索引值与 mins 中存的索引值是否相等，是则出栈
     *
     * 时间复杂度：O (1)
     * 空间复杂度 ：< O (n)
     */

    private void push(int num) throws Exception {
        data.add(num);
        if (mins.size() == 0) { // 初始化 mins 栈
            mins.add(0);
        } else {
            // mins 辅助栈push最小值的索引
            int minValue = getMin();
            if (num < minValue) {
                mins.add(data.size() - 1); // 将最小值在data栈中的索引 push 到 mins 栈中
            }
            System.out.print("push完后mins栈中的索引为：");
            for (int index : mins) {
                System.out.print(index + " ");
            }
        }
    }

    private int pop() throws Exception {
        // 栈为空，则抛出异常
        if (data.size() == 0) {
            throw new Exception("stack is empty!");
        }

        // pop 时先获取索引
        int popIndex = data.size() - 1;

        // 获取 mins 辅助栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);

        // 若 pop 出去的索引就是最小值索引，mins 才出栈
        if (popIndex == minIndex) {
            mins.remove(mins.size() - 1);
        }

        System.out.print("pop后mins栈中的索引为：");
        for (int index : mins) {
            System.out.print(index + " ");
        }

        return data.remove(data.size() - 1);
    }

    /**
     *
     * @return 通过 mins 栈中最小值的索引得到 data 栈中对应的值
     * @throws Exception
     */
    private int getMin() throws Exception {
        // 栈为空，则抛出异常
        if (data.size() == 0) {
            throw new Exception("stack is empty!");
        }

        // 获取 mins 栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        return data.get(minIndex);
    }

    @Test
    public void testStackWithMin() throws Exception {
        StackWithMin stackWithMin1 = new StackWithMin();
        
        /* 思路 2 */
        StackWithMin stackWithMin = new StackWithMin();
        stackWithMin.push(6);
        stackWithMin.push(2);
        stackWithMin.push(2);   

        System.out.println();
        int pop = stackWithMin.pop();
        System.out.print("data 栈中pop的元素：" + pop);
        System.out.println();
        int min = stackWithMin.getMin();
        System.out.print("data 栈中getMin为：" + min);
    }
}