脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 30. 包含min函数的栈，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

剑指 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栈顶的元素，此时@H_360_42@将当前栈顶元素再次压入栈顶

代码

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();
    }
}

复杂度分析

• @R_175_1304@：(O(1))
• 空间复杂度：(O(N))

脚本宝典总结

以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 30. 包含min函数的栈全部内容，希望文章能够帮你解决力扣 - 剑指 Offer 30. 包含min函数的栈所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。