题解 | #包含min函数的栈#

包含min函数的栈

http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49

方法一:辅助栈
核心思想
普通栈的 函数的复杂度为,满足题目要求。但获取栈最小值的 函数需要遍历整个栈,复杂度为,所以本题的主要目的就在于优化对栈的最小值的获取,这可以通过使用一个具有单调性的辅助栈来实现。
具体思路:
数据栈:数据栈用于存储所有元素,保证函数的正常逻辑。
辅助栈:辅助栈中存储数据栈中所有降序的元素。栈具有先进后出的特点,所以一个值压入栈中后,只要未被弹出,所有在它之后进行压栈的小于该值的元素都不会成为最小值,可以不压入辅助栈,这可以保证辅助栈栈顶即为数据栈中所有数据中的最小值。

函数说明: 压栈时,只有辅助栈为空,或该数值不大于辅助栈栈顶元素,才对辅助栈进行压栈。 出栈时,如果数据栈栈顶元素与辅助栈栈顶元素相等,说明该数值被弹出,也需要同时对辅助栈进行出栈。
核心代码

class Solution {
private:
    stack<int> sk;
    stack<int> help;
public:
    void push(int value) {
        sk.push(value);
        //保证辅助栈的单调性
        if(help.empty() || value <= help.top()) {
            help.push(value);
        }
    }
    void pop() {
        //如果辅助栈栈顶值与数据栈栈顶值相等则出栈
        if(help.top() == sk.top()) {
            help.pop();
        }
        sk.pop();
    }
    int top() {
        return sk.top();
    }
    int min() {
        return help.top();//辅助栈栈顶既为最小值
    }
};

复杂度分析
时间复杂度:,对单个操作,四个函数的时间复杂度均为常数级别
空间复杂度:,最坏情况下,辅助栈也需要存储所有元素,使用空间

方法二:单个栈
核心思想
也可以使用单个栈完成功能,但此时的栈不是存储数据,而是存储数据与当前最小值的差值,并另外存储一个最小值
函数说明: :压栈时,当栈为空时,存储最小值,压入差值0。栈不为空时,压入数据与当前最小值的差值,如果差值为负,则更新最小值 :出栈时,如果此时栈顶值为负数,说明此处发生的最小值的变化,需要更新最小值。 :如果栈顶值为负数,说明最小值在此处更新,此时返回最小值即可。如果栈顶值为正数,即为最小值与数据的差值,相加后进行返回 :直接返回存储的最小值即可
核心代码

class Solution {
private:
    stack<long> sk;//记录与最小值差值,由于可能大于INT_MAX,使用long
    long tmin;//记录最小值
public:
    void push(int value) {
        if(sk.empty()) {
            //当栈为空,最小值即为当前值,差值为0
            sk.push(0);
            tmin = value;
        } else {
            //压入与最小值的差值
            sk.push(value - tmin);
            if(value < tmin) {
                //如果当前值小于最小值,进行更新
                tmin = value;
            }
        }
    }

    void pop() {
        if(sk.top() < 0) {
            //差值为负数,说明当前位置最小值发生改变,需要改回该元素压入前的最小值
            tmin -= sk.top();
        }
        sk.pop();
    }

    int top() {
        if(sk.top() < 0) {
            return tmin;//此时最小值刚进行更新
        } else {
            return tmin + sk.top();
        }
    }
    int min() {
        return tmin;
    }
};

复杂度分析
时间复杂度:,对单个操作,四个函数的时间复杂度均为常数级别
空间复杂度:,只使用了常数个变量

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务