美文网首页
面试题30(剑指offer)--包含min函数的栈

面试题30(剑指offer)--包含min函数的栈

作者: Tiramisu_b630 | 来源:发表于2019-08-19 16:23 被阅读0次

题目:

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。

思路:

借助一个辅助栈存储最小值,这样就能在O(1)时间内取得最小值。

代码:

    public class MinStack {
    Stack<Integer> mainStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();//存储最小值
    public void put(int node) {
        mainStack.push(node);
        if (minStack.empty() || node < minStack.peek()) {
            minStack.push(node);
        } else {
            minStack.push(minStack.peek());
        }
    }
    public void pop() {
        if (!minStack.empty() && !mainStack.empty()) {
            mainStack.pop();
            minStack.pop();
        }
    }
    public int min() {
        if (!minStack.empty() && !mainStack.empty()) {
            return minStack.peek();
        }
        return -1;
    }
}

相关文章

网友评论

      本文标题:面试题30(剑指offer)--包含min函数的栈

      本文链接:https://www.haomeiwen.com/subject/irhesctx.html