[头条]笔试题——最小栈

灰太狼 2023-09-28 17:57 18阅读 0赞

![723fd41a42614bbc9b976bd9edc97da3.png][]

![1196938b101147f3b27a898655f460fc.png][]

> 解法一：（相对解法二，会非常鸡肋）

思路：

*  由于获取堆栈最小元素时间复杂度为O(1)，所有用创建一个变量min用来存放最小值
 *  将存放最小值的变量min设为Integer.MAX\_VALUE
 *  push方法里，每push一次用min比较
 *  创建两个栈，第一个栈用来存放数据，第二栈用来通过变量第一个栈而得出最小数据的零时栈

class MinStack {
        public Stack<Integer> stack;
        public Stack<Integer> stackTmp;
        public MinStack() {
            stack = new Stack<>();
            stackTmp = new Stack<>();
        }
        //先赋最大值
        public int min = Integer.MAX_VALUE;
        public void push(int val) {
            //有比他小的就赋值
            if(val < min){
                min = val;
            }
            stack.push(val);
        }
        
        public void pop() {
            if(stack.pop() == min){
                //被pop后min需要重新赋值，依旧用最大值
                min = Integer.MAX_VALUE;
                //将所有元素转移到stackTmp，目的是为了让min重新与所有元素比较
                while(!stack.empty()){
                    int tmp = stack.pop();
                    if(tmp < min){
                        min = tmp;
                    }
                    stackTmp.push(tmp);
                }
                //再转移到stack
                while(!stackTmp.empty()){
                    stack.push(stackTmp.pop());
                }
            }
        }
        
        public int top() {
            return stack.peek();
        }
        
        public int getMin() {
            return min;
        }
    }

--------------------

> 解法二：（分析如下）

![90513709f88648f59ce6574a86f0f3a8.png][]

![29b9e3639a73443f9a94a6d307dff66f.png][]

![83e51dbe0aeb45fd819cb51f0cfadee2.png][]

![a9d5487552e74d409b80c91c714be9d5.png][] ![525c076fcc3843759c2d98e22cf56356.png][]

![f54e0a5cfab64112ae40b52d4f59a73f.png][]

> 代码如下：

class MinStack {
        Stack<Integer> stack;//普通栈
        Stack<Integer> stackMin;//最小栈
        public MinStack() {
            stack = new Stack<>();
            stackMin = new Stack<>();
        }
        //压栈
        public void push(int val) {
            //给最小站赋初值
            if(stackMin.empty()){
                stackMin.push(val);
            }
            //若不是初值，先判断是否小于等于（等于是以防pop后为空）最小栈栈顶元素，若是，才给最小栈压栈
            else if(stackMin.peek() >= val){
                    stackMin.push(val);
            }
            stack.push(val);
        }
        
        public void pop() {
            if((int)stackMin.peek() == (int)stack.peek()){
                stackMin.pop();
            }
            stack.pop();
        }
        
        public int top() {
            return stack.peek();
        }
        
        public int getMin() {
            return stackMin.peek();
        }
    }

[723fd41a42614bbc9b976bd9edc97da3.png]: https://img-blog.csdnimg.cn/723fd41a42614bbc9b976bd9edc97da3.png
[1196938b101147f3b27a898655f460fc.png]: https://img-blog.csdnimg.cn/1196938b101147f3b27a898655f460fc.png
[90513709f88648f59ce6574a86f0f3a8.png]: https://img-blog.csdnimg.cn/90513709f88648f59ce6574a86f0f3a8.png
[29b9e3639a73443f9a94a6d307dff66f.png]: https://img-blog.csdnimg.cn/29b9e3639a73443f9a94a6d307dff66f.png
[83e51dbe0aeb45fd819cb51f0cfadee2.png]: https://img-blog.csdnimg.cn/83e51dbe0aeb45fd819cb51f0cfadee2.png
[a9d5487552e74d409b80c91c714be9d5.png]: https://img-blog.csdnimg.cn/a9d5487552e74d409b80c91c714be9d5.png
[525c076fcc3843759c2d98e22cf56356.png]: https://img-blog.csdnimg.cn/525c076fcc3843759c2d98e22cf56356.png
[f54e0a5cfab64112ae40b52d4f59a73f.png]: https://img-blog.csdnimg.cn/f54e0a5cfab64112ae40b52d4f59a73f.png