Leetcode 155. 最小栈

题目:

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

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

辅助栈解法(1)-辅助栈与数据栈大小一致,入栈出栈同步

因为需要每次都能够取到栈中的最小值,肯定是不能全部出栈之后遍历再对比了,只能考虑其他的办法来获取最小值.

那就需要以空间换时间,新增一个辅助栈,数据栈每次入栈时的数据都与辅助栈的栈顶进行对比,如果小于栈顶,则在辅助栈压入当前数据,否则继续压入辅助栈中的最小值,此时辅助栈的栈顶永远都是最小值.

如图:

//辅助栈与数据栈大小一致,入栈出栈同步
    class MinStack {
        Stack<Integer> data;
        //声明一个辅助栈
        Stack<Integer> helper;

        /** initialize your data structure here. */
        public MinStack() {
            data = new Stack();
            helper = new Stack();
        }

        public void push(int x) {
            data.add(x);
            //如果新加入的值比原来的最小值小的话,则压入X,否则继续压入原有最小值
            if(helper.isEmpty() || helper.peek() >= x){
                helper.add(x);
            }else{
                helper.add(helper.peek());
            }
        }

        public void pop() {
            //出栈需要一起出栈
            if(!data.isEmpty()){
                data.pop();
                helper.pop();
            }

        }

        public int top() {
            //返回最上级值即可
            return data.peek();
        }

        public int getMin() {
            //返回辅助栈的最小值
            return helper.peek();
        }
    }

复杂度

空间复杂度:O(N);

时间复杂度:O(1);

辅助栈解法(2)-辅助栈与数据栈大小不一致,入栈出栈不同步

新增一个辅助栈,每次只有新增的值小于等于当前辅助栈栈顶值才会push进入,需要注意的是pop的时候,如果数据栈出栈的值等于当前栈顶值时,则一起出栈,此时辅助栈中的栈顶值还是最小值.

如图:

Stack<Integer> data;
        //声明一个辅助栈
        Stack<Integer> helper;

        /** initialize your data structure here. */
        public MinStack2() {
            data = new Stack();
            helper = new Stack();
        }

        public void push(int x) {
            data.add(x);
            //如果新加入的值比原来的最小值小的话,则压入X,否则继续压入原有最小值
            if(helper.isEmpty() || helper.peek() >= x){
                helper.add(x);
            }
        }

        public void pop() {
            if(!data.isEmpty()){
                //如果数据栈值等于现在辅助栈最小值,则需要将辅助栈也出栈
                if (data.peek().equals(helper.peek())) {
                    helper.pop();
                }
                data.pop();
            }

        }

        public int top() {
            //返回最上级值即可
            return data.peek();
        }

        public int getMin() {
            //返回辅助栈的最小值
            return helper.peek();
        }

复杂度

空间复杂度:O(n)

时间复杂度:O(1)

单栈解法-新增变量存储最小值

如果只能使用一个栈的话,我们想到了使用一个最小值来存储最小值,在持续入栈的情况下是没有问题的,例如入栈2,3,1,0 此时最小值为0,但是一旦我们将最小值出栈之后,将会导致倒数第二小的值丢失,此时最小值依旧是0,无法更新为1,那我们如果只有一个栈的话,只能将每次的最小值一起压入单栈.出栈的话就要考虑对比是否是最小值,如果是和min一样的最小值,则将出两个栈,并将min值更新为第二个出栈的值

如图:

		 Stack<Integer> data;
        //设置为最大值,以免影响判断
        int minValue = Integer.MAX_VALUE;

        /** initialize your data structure here. */
        public MinStack3() {
            data = new Stack();
        }

        public void push(int x) {
            //相当于每次压栈的时候,如果有比之前的值更小的值的时候,将上次的最小值先压入,再压入真实data值
            if (x <= minValue) {
                data.add(minValue);
                minValue = x;
            }
            data.add(x);
        }

        public void pop() {
            if(!data.isEmpty()){
                //因为前面多压了数值,如果出栈的值正好是当前最小值,则需要将倒数第二小的值一起出栈,并且将最小值更新
                if (data.pop() == minValue) {
                    minValue = data.pop();
                }
            }

        }

        public int top() {
            //返回最上级值即可
            return data.peek();
        }

        public int getMin() {
            //返回辅助栈的最小值
            return minValue;
        }
    }