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

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

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

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

思路

以空间换时间,采用辅助栈。
辅助栈可以分为同步辅助栈和不同步辅助栈两种。

同步辅助栈:
额外设置一个栈,同步保存当前数据栈的最小值,该辅助栈所push的值递减(非严格递减),pop与push操作与数据栈同步。
getMin时间复杂度O(1),空间复杂度O(n)。

不同步辅助栈:
额外设置一个栈,保存当前数据栈的最小值,同样也是递减栈,pop与push操作与数据栈不同步:
仅当 数据栈push操作的数据 <= 辅助栈的栈顶值(最小值),辅助栈才进行push更新。
仅当 数据栈pop操作的数据 == 辅助栈的栈顶值(最小值),辅助栈才进行pop更新。
getMin时间复杂度O(1),空间复杂度O(n)。

代码

  • 同步辅助栈
import java.util.*;

class MinStack {

    private Stack<Integer> data;
    
    private Stack<Integer> helper;
    
    /** initialize your data structure here. */
    public MinStack() {
        data = new Stack<Integer>();
        helper = new Stack<Integer>();
    }
    
    public void push(int x) {
        data.push(x);
        if(helper.isEmpty() || x<helper.peek()) {
            helper.push(x);
        } else {
            helper.push(helper.peek());
        }
    }
    
    public void pop() {
        if(!data.isEmpty()) {
            data.pop();
            helper.pop();
        }
    }
    
    public int top() {
        if(!data.isEmpty()) {
            return data.peek();
        }
        throw new RuntimeException("栈空,栈顶无元素");
    }
    
    public int getMin() {
        if(!data.isEmpty()) {
            return helper.peek();
        }
        throw new RuntimeException("栈空,栈无最小值");
    }
}
  • 不同步辅助栈
import java.util.*;

class MinStack {

    private Stack<Integer> data;
    
    private Stack<Integer> helper;
    
    /** initialize your data structure here. */
    public MinStack() {
        data = new Stack<Integer>();
        helper = new Stack<Integer>();
    }
    
    public void push(int x) {
        data.push(x);
        if(helper.isEmpty() || x<=helper.peek()) {
            helper.push(x);
        }
    }
    
    public void pop() {
        if(!data.isEmpty()) {
            if(data.peek().equals(helper.peek())) {
                helper.pop();
            }
            data.pop();
        }
    }
    
    public int top() {
        if(!data.isEmpty()) {
            return data.peek();
        }
        throw new RuntimeException("栈空,栈顶无元素");
    }
    
    public int getMin() {
        if(!data.isEmpty()) {
            return helper.get(helper.size()-1);
        }
        throw new RuntimeException("栈空,栈无最小值");
    }
}

笔记

  1. 辅助栈使用ArrayList代替Stack难以看到优势,反而降低编码效率;
    ArrayList扩容因子为1.5,Stack扩容因子为2;
    Java集合框架图:
     leetcode| 155. 最小栈 算法

  2. data.peek().equals(helper.peek())
    包装类型为引用类型,不能直接等于号比较。
    Integer包装类仅在比较的整数值在-128 - 127时可以比较,
    Integer相关源码:
    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

    private static class IntegerCache {
        static final int low = -128;
        static final int high;
        static final Integer cache[];

        static {
            // high value may be configured by property
            int h = 127;
            String integerCacheHighPropValue =
                sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
            if (integerCacheHighPropValue != null) {
                try {
                    int i = parseInt(integerCacheHighPropValue);
                    i = Math.max(i, 127);
                    // Maximum array size is Integer.MAX_VALUE
                    h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                } catch( NumberFormatException nfe) {
                    // If the property cannot be parsed into an int, ignore it.
                }
            }
            high = h;

            cache = new Integer[(high - low) + 1];
            int j = low;
            for(int k = 0; k < cache.length; k++)
                cache[k] = new Integer(j++);

            // range [-128, 127] must be interned (JLS7 5.1.7)
            assert IntegerCache.high >= 127;
        }

        private IntegerCache() {}
    }

当数值在-128 - 127时,静态内部类IntegerCache使用同一cache数组共享数据。

链接:https://leetcode-cn.com/problems/min-stack

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄