当前位置：首页 > article >正文

打卡算法题：155. 最小栈 --- 从193ms 到 4 ms的优化

article 2025/1/5 14:34:06

155. 最小栈

设计一个支持 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() {
        
    }
}

方案一：

这里可以使用一个辅助栈进行存储最小值,也就是在这里push的时候在辅助栈中存储前面部分的最小值作为该区间的最小值。

    class MinStack {

        private LinkedList<Integer> stack;

        private LinkedList<Integer> minStack;

        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        public void push(int val) {
            stack.push(val);
            int min = val;
            for (int element: minStack){
                if(element < min){
                    min = element;
                }
            }
            minStack.push(min);
        }

        public void pop() {
            minStack.pop();
            stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

但是这种方式占用的内存和执行时长都太长了，需要换一种方案进行优化：

方案二

这里相比于之前是不用进行遍历的，从O（n）变成了O(1)

import java.util.Stack;

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop(); 
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

那么目前就比193ms要快的多了。

当然这里还可以继续提高

import java.util.LinkedList;
    class MinStack {

        private LinkedList<Integer> stack;

        private LinkedList<Integer> minStack;

        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        public void push(int val) {
            stack.push(val);
            if (minStack.isEmpty() || val <= minStack.peek()) {
                minStack.push(val);
            }
        }

        public void pop() {
            // 如果栈顶元素和 minStack 栈顶元素相等，则同时弹出 minStack 的栈顶
            if (stack.peek().equals(minStack.peek())) {
                minStack.pop();
            }
            stack.pop(); // 弹出元素
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

这里继续使用LinkedList，此处的执行时间还能更快一些，内存消耗也确实减少了一些

方案三

    class MinStack {

        private LinkedList<int[]> stack;

        public MinStack() {
            stack = new LinkedList<>();
        }

        public void push(int val) {
            if (stack.isEmpty()){
                stack.push(new int[]{val,val});
            }else{
                int currentMin = stack.peek()[1];
                stack.push(new int[]{val, Math.min(currentMin, val)});
            }
        }

        public void pop() {
            stack.pop();
        }

        public int top() {
            if (stack.isEmpty()){
                return 0;
            }else{
                return stack.peek()[0];
            }
        }

        public int getMin() {
            if (stack.isEmpty()){
                return 0;
            }else{
                return stack.peek()[1];
            }
        }
    }

这里其实如果不用辅助栈，还可以使用数组的方式进行存储两个值，以这种方式，速度整体上其实并没有太大的变化。

方案四

import java.util.Stack;

class MinStack {
    private Stack<Long> stack; 
    private long min;         

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(0L); 
            min = val;     
        } else {
            stack.push((long) val - min);
            if (val < min) {
                min = val;
            }
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;

        long diff = stack.pop();
        if (diff < 0) {
            min = min - diff; 
        }
    }

    public int top() {
        long diff = stack.peek();
        if (diff > 0) {
            return (int) (min + diff); 
        } else {
            return (int) min;
        }
    }

    public int getMin() {
        return (int) min;
    }
}

还可以使用存储差值的方式，这样就可以不用直接去存储值和最小值了，但是用数学思维比较多，不太容易想到。