定义一个能获取最小值的栈

发表于 分类于 阅读次数：

题目

实现一个特殊的栈,在基本栈的基础上,增加返回栈中最小元素的方法,要求时间复杂度为O(1)

示例

stack:{4,3,9,6}

getMin() return 3;

思路

有的兄弟萌一开始可能会想直接在push的时候用一个全局变量记录最小值，但仔细想想，在没有pop的情况下是没有问题的，一旦pop了最小值就可能随之改变，如果单用一个变量时无法记录”之前”的最小值的。所以我们有了下面的思路

1.我们有两个栈，一个用于存放数据，一个用于存放最小值，每当要存数据，两个栈都进行更新（入栈）

2.若最小值栈的栈顶小于新的数据，则最小值栈重复存入其栈顶的值

3.若最小值栈的栈顶大于新的数据，则最小值栈存入新的数据

4.当pop时两个栈同时pop，即可保证最小值栈中存放的是当前数据栈中存在的数据

push过程

push过程

下面看下实际代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static class MinStack {
        private Stack<Integer> DataStack;
        private Stack<Integer> MinsStack;

        public MinStack() {
            this.DataStack = new Stack<>();
            this.MinsStack = new Stack<>();
        }

        public void push(int newNum) {
            if(this.MinsStack.isEmpty()) {
                this.MinsStack.push(newNum);
            } else if(this.getMin() > newNum) {   //小于当前最小值

            } else {    //大于当前最小值
                int newMin =this.MinsStack.peek();
                this.MinsStack.push(newMin);
            }
            this.DataStack.push(newNum);
        }


        public int pop() {
            if(this.DataStack.isEmpty()) {
                throw new IllegalArgumentException();
            }
            this.MinsStack.pop();
            return DataStack.pop();
        }

        public int getMin() {
            if(this.MinsStack.isEmpty())
                throw new IllegalArgumentException();
            return this.MinsStack.peek();
        }
    }