力扣 - 剑指 Offer 30. 包含min函数的栈

题目

思路1

使用一个辅助栈min_stack，用来维护栈的最小的元素
每次添加元素入栈时候，data_stack和min_stack都要同时维护
data_stack按照正常的栈压入和弹出顺序，但是min_stack栈不一样，因为要能获取当前栈的最小元素：
- 如果栈是空的，直接入栈
- 如果栈不是空的，分两种情况：
  1. 待入栈的元素x小于min_stack栈顶的元素，此时直接将x压入min_stack栈
  2. 待入栈的元素x大于min_stack栈顶的元素，此时将当前栈顶元素再次压入栈顶

代码

class MinStack {

    LinkedList<Integer> data_stack;

    // min_stack为辅助栈

    LinkedList<Integer> min_stack;

    public MinStack() {

        // 初始化

        data_stack = new LinkedList<>();

        min_stack =  new LinkedList<>();

    }

    public void push(int x) {

        data_stack.push(x);

        // 入栈的时候要判断辅助栈是否为空，空的话直接push即可

        if (!min_stack.isEmpty()) {

            // 判断待入栈的元素x是否大于min_stack栈顶元素，如果小于直接入栈；若大于，则将原来栈顶的元素再次入栈一次

            if (x < min_stack.peek()) {

                min_stack.push(x);

            } else {

                min_stack.push(min_stack.peek());

            }

        } else {

            min_stack.push(x);

        }

    }

    public void pop() {

        // 如果pop的话直接弹出去

        // 这里不用担心min_stack辅助栈的最小元素被pop出去，因为min_stack和data_stack是一一对应的，同时pop出去对获取当前栈的最小值没有影响

        data_stack.pop();

        min_stack.pop();

    }

    public int top() {

        // 查看当前栈的栈顶也是直接peek

        return data_stack.peek();

    }

    public int min() {

        // 辅助栈的栈顶元素就是当前栈中的最小的元素

        return min_stack.peek();

    }

}

复杂度分析

时间复杂度：\(O(1)\)
空间复杂度：\(O(N)\)

巴特西

力扣 - 剑指 Offer 30. 包含min函数的栈

题目

思路1

代码

复杂度分析

最新文章

热门文章