剑指offer-20-包含min函数的栈

包含min函数的栈_牛客网

https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

在看到这道题目的时候第一反应是要用一个最小值来保留当前栈中最小值,但是也能够很快地意识到比较麻烦的地方在于pop的时候怎么更新min值,看了别人的题解之后都是使用了另外一个栈来保持在入栈过程中曾经做过最小值的值,pop的时候判断两个栈顶元素是否一致,一致的话都要pop,在这种情况下取最小值需要从保存最小值的栈顶元素取值

另外一点是这道题目也顺便联系java中Stack的常用的方法empty(); push(); pop();peek();比较坑爹的时元素需要定义为static的并且要手动初始化,不然list会被初始化为null

我自己的想法是不希望用另外一个栈,那么为了实现这一目的,在栈中需要保留冗余的曾经的最小值,这样能够比较方便到找到当前的此小值,具体见下面的代码

import java.util.Stack;

public class Solution {

    //需要这样写来初始化stack,不然会报空指针push的时候
    private static Stack<Integer> stack = new Stack<Integer>();
    private static Intege

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

小白刷剑指offer 文章被收录于专栏

跟着小白一起刷剑指offer,通过讨论加深印象吧~ 没有人不学习就能够掌握知识,知识就是需要学习的~

全部评论
push一个值之后,再push一个更小值,此时再pop两次,再取top就会有问题吧,栈会多存一次次小值 比如说push3 push4 push2 push1,此时最小是1,栈内是:343221,然后我pop后栈就变成了:34322,最小值变成2,再pop就变成,3432,此时取top就是2,然而答案应该是4
1 回复 分享
发布于 2021-05-16 19:53
666
点赞 回复 分享
发布于 2020-05-23 18:49
放的时候好像不需要判断空,直接把最大值放进去,并且pop也不需要判断是否等于1了
点赞 回复 分享
发布于 2020-05-12 00:28
1 2 3 4 0 1 0
点赞 回复 分享
发布于 2020-04-26 21:53
请教两个问题: 1 实例变量没必要定义成 static吧 2 题干中说的当为空的时候不能调用top(), min(), pop() 等方法,前两个答主好像并没有处理
点赞 回复 分享
发布于 2020-04-21 10:01
非常好的思路,做了下修改更简洁: public void push(int node){ if(node<=min){ stack.push(minElement); minElement=node; } stack.push(node); } public void pop(){ if(stack.pop()==minElement)minElement=stack.pop(); }
点赞 回复 分享
发布于 2020-02-28 06:36
思路不对吧,假如第一次弹次小值,第二次弹最小值,再弹的时候已经是第三小的值了,然而你的结果会是第二小的值
点赞 回复 分享
发布于 2020-01-20 22:09
14行那,是不是应该是.     if(node < =minElement){ 不然会出bug,还有就是剩一个的时候可能也会出,没仔细想
点赞 回复 分享
发布于 2019-09-17 22:30
这个是不是连续两次弹出最小值后,存储的最小值是错误的啊?😰
点赞 回复 分享
发布于 2019-09-09 21:22

相关推荐

xdm&nbsp;早上喝奶茶差点喷出来。事情是这样的,我们班有个哥们儿,简称&nbsp;L,去年秋招拿了字节sp,专业方向是后端。我们当时都震惊:这哥们儿平时课上从来不发言,期末小组作业基本是划水的那种,刷题平台&nbsp;commit记录我点进去看过,绿格子稀稀拉拉。但他面试一路绿灯。一面二面三面&nbsp;hr&nbsp;面,全过,给的还是sp。当时班级群里恭喜他的、问他经验的、约饭的,热闹了一周。他说自己"运气好,准备充分"。我们都信了,直到三月初他入职。入职第二周开始,班里另一个进字节的同学W(在隔壁组的)开始跟我他的不对劲。一开始是写代码慢,后来写不出来,再后来是组里&nbsp;mentor&nbsp;让他fix&nbsp;一个简单&nbsp;bug&nbsp;都搞了一下午没动静。最离谱的是上周。W&nbsp;说他们大部门搞了个新人分享会,让新人讲一下自己负责模块的设计思路。L&nbsp;上去讲了&nbsp;20分钟,全程念稿子,问答环节别人随便问一个"那你这里为什么用&nbsp;Redis&nbsp;不用&nbsp;Memcached",他直接卡&nbsp;30秒说"这个我回去再确认一下"。会后他&nbsp;mentor&nbsp;直接找&nbsp;leader&nbsp;谈,leader&nbsp;找&nbsp;hr&nbsp;谈,hr调出了他面试录像,全程对比口型和回答节奏,发现他二三面有大量时长在偷偷看屏幕外(推测开了双机位&nbsp;AI&nbsp;答题)。(这段是&nbsp;W后来转述给我的,他自己也是听他组里同事八卦来的)昨天下班前,W&nbsp;告诉我L&nbsp;被辞退了,让他自己走,不走就走仲裁但会发函到学校。L&nbsp;现在已经回学校了,朋友圈仅三天可见。我说真的,我不是个心眼小的人,但是我看到这个消息的时候真的有种"嗯,挺好"的感觉。去年秋招我投字节后端,简历挂。我准备了八个月,背&nbsp;八股&nbsp;+&nbsp;刷&nbsp;500&nbsp;题&nbsp;+项目改了三版,连面试机会都没拿到。班里这哥们儿凭着一个外挂上岸,最后还是被甩出来了。不是说作弊就一定会被发现,但是当面试拿到的&nbsp;offer远远超出真实能力的时候,迟早会有这一天。试用期三个月不是给你过家家的,是真的要写代码、要在会议上回答问题、要扛需求的。我现在反而有点同情他。同情他相信"上岸就是终点"。发出来不是为了嘲笑谁,就是想说给那些正在被身边作弊上岸的同学搞得很&nbsp;emo&nbsp;的&nbsp;uu&nbsp;们听——别急,回旋镖很长,但它一定会回来。你继续刷你的题,写你的项目,背你的八股。该是你的迟早是你的,不是你的早晚还得还回去。xdm&nbsp;共勉。
牛客12588360...:我不想评论面试方式,作弊是绝对不对的,但是你八股加刷题也不过是个做题小子,他穿帮纯粹是他菜,你也没有高明到哪里去
点赞 评论 收藏
分享
评论
37
2
分享

创作者周榜

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