【Java题解】面试题 03.02. 栈的最小值

请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例:

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

方法一:
使用辅助栈。定义两个栈,stack1, stakc2(辅助栈)

  1. stack2栈用于存储stack1中对应元素的下面的元素的最小值。
  2. 每入栈一个元素,再stack2中,对应位置,判断一下,它和之前辅助栈中的元素谁更小,然后更新辅助栈中的元素。
  3. 这样就可以让stack2栈中的元素与stack1一一对应,并且是以当前元素为栈顶的栈中的最小值。

代码:

class MinStack {

    Deque<Integer> stack1, stack2;
    
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void push(int x) {
        stack1.addLast(x);
        if (stack2.isEmpty()) stack2.addLast(x);
        else {
            stack2.addLast(Math.min(x, stack2.getLast()));
        }
    }
    
    public void pop() {
        stack1.removeLast();
        stack2.removeLast();
    }
    
    public int top() {
        return stack1.getLast();
    }
    
    public int getMin() {
        return stack2.getLast();
    }
}

时间复杂度:O(1)
空间复杂度:O(n)

上一篇:拓端tecdat|R语言聚类有效性:确定最优聚类数分析IRIS鸢尾花数据和可视化


下一篇:数据挖掘与分析练习——蘑菇(涉及聚类、降维)