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

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 30.包含min函数的栈

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

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

示例:

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

提示:

  • 1、各函数的调用总次数不超过 20000 次

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

如果只使用一个来实现 min 函数会发现 push()pop() 操作可以达到 O(1) 的时间复杂度,但由于获取最小值需要遍历整个栈,所以 min 的操作的时间复杂度是 O(N) 级别,不满足要求。

压缩时间的一个方法是增加额外的空间,即再使用一个辅助栈

  • 数据栈:存储所有元素, push()pop()top() 操作都使用数据栈来完成
  • 辅助栈:在辅助栈中,每次压入的元素只能比辅助栈的栈顶元素更小或者相等,如果更大,则重复再压入辅助栈的栈顶元素。
push() 函数

剑指 Offer 30. 包含min函数的栈.004

剑指 Offer 30. 包含min函数的栈.005

剑指 Offer 30. 包含min函数的栈.006

剑指 Offer 30. 包含min函数的栈.007

剑指 Offer 30. 包含min函数的栈.008

剑指 Offer 30. 包含min函数的栈.009

剑指 Offer 30. 包含min函数的栈.010

剑指 Offer 30. 包含min函数的栈.011

剑指 Offer 30. 包含min函数的栈.012

剑指 Offer 30. 包含min函数的栈.013

剑指 Offer 30. 包含min函数的栈.014

剑指 Offer 30. 包含min函数的栈.015

剑指 Offer 30. 包含min函数的栈.016

pop()函数

数据栈和辅助栈同时执行 pop() 操作。

剑指 Offer 30. 包含min函数的栈.020

剑指 Offer 30. 包含min函数的栈.021

top()函数

直接返回数据栈的栈顶元素。

剑指 Offer 30. 包含min函数的栈.022

min() 函数

直接返回辅助栈的栈顶元素。

剑指 Offer 30. 包含min函数的栈.018

2、规律

需要维护好辅助栈的元素,每次压入元素时都需要和辅助栈的栈顶元素对比,这样才能确保辅助栈的栈顶元素永远是最小的,执行 min() 函数是才可以做到 O(1) 的时间里获取到最小的元素。

3、匹配

栈。

4、边界

注意辅助栈为空的情况。

三、动画描述

四、图片描述

剑指 Offer 30. 包含min函数的栈.002

剑指 Offer 30. 包含min函数的栈.003

剑指 Offer 30. 包含min函数的栈.004

剑指 Offer 30. 包含min函数的栈.005

剑指 Offer 30. 包含min函数的栈.006

剑指 Offer 30. 包含min函数的栈.007

剑指 Offer 30. 包含min函数的栈.008

剑指 Offer 30. 包含min函数的栈.009

剑指 Offer 30. 包含min函数的栈.010

剑指 Offer 30. 包含min函数的栈.011

剑指 Offer 30. 包含min函数的栈.012

剑指 Offer 30. 包含min函数的栈.013

剑指 Offer 30. 包含min函数的栈.014

剑指 Offer 30. 包含min函数的栈.015

剑指 Offer 30. 包含min函数的栈.016

剑指 Offer 30. 包含min函数的栈.017

剑指 Offer 30. 包含min函数的栈.018

剑指 Offer 30. 包含min函数的栈.019

剑指 Offer 30. 包含min函数的栈.020

剑指 Offer 30. 包含min函数的栈.021

剑指 Offer 30. 包含min函数的栈.022

剑指 Offer 30. 包含min函数的栈.023

剑指 Offer 30. 包含min函数的栈.024

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class MinStack {
    // 构建两个栈
    // stack1 代表数据栈
    // stack2 代表辅助栈
    Stack<Integer> stack1,stack2;

    public MinStack() {
        // 初始化
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        // 数据栈直接压入 x
        stack1.add(x);
        // 如果辅助栈是空,也直接压入 x
        if(stack2.empty()){
            stack2.add(x);
        }else{
            // 如果辅助栈的栈顶元素不小于 x,也直接压入 x
            if(stack2.peek() >= x){
                stack2.add(x);
            }else{
                //如果辅助栈的栈顶元素小于 x,则压入辅助栈原来的栈顶元素
                stack2.add(stack2.peek());
            }
        }
    }

    public void pop() {
        // 数据栈直接 pop
        stack1.pop();
        // 辅助栈直接 pop
        stack2.pop();
    }

    public int top() {
         // 返回数据栈的栈顶元素
        return stack1.peek();
    }

    public int min() {
         // 返回辅助栈的栈顶元素
        return stack2.peek();
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(1)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

发表评论

邮箱地址不会被公开。 必填项已用*标注