一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 791|回复: 9
收起左侧

[CareerCup] 【第四轮】4.13 - 4.19 Career Cup 3.2

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-14 10:52:49 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
3.2 How would you design a stack which, in addition to push and pop, also has a
function min which returns the minimum element? Push, pop and min should
all operate in O(1) time.

解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改

A30041839 发表于 2015-4-15 16:40:39 | 显示全部楼层
[solution]
use an additional min_stack to keep track of the min elements. when pushing number x to the stack, push x to min_stack if:
1)min_stack is empty
2)x is less or equal to the top of min_stack
when popping an element from stack, pop it from min_stack if:
1) x is equal to the top of min_stack
[time]
push, pop, min operates in O(1) time
[space]
O(n)
[gist]
https://gist.github.com/A30041839/590ee2dc06a2e6b6b010
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-15 22:16:40 | 显示全部楼层
[解题思路]
额外建立一个stack用来保存每一次push元素进入一个stack时候,此时的min值,这样子就可以完成O(1)的时间复杂度来返回min
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/ee5393fed97f741d9030
然后有一个疑惑是gist连接的代码里面19行,应该是s2.pop()还是s2.peek()
【test case】
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-16 05:18:28 | 显示全部楼层
【解题思路】
use a stack to store the  minum value of the   stack,   
* if push  data  < minstack.top   then push the data to minstack
* if pop() =  minstack.top  then pop  data from minstack
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/8a7314011cf0a90b925a
【test case】
https://gist.github.com/michaelniu/8a7314011cf0a90b925a(main)
code is runable
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-16 21:21:33 | 显示全部楼层
【解题思路】
# use an extra min stack to store the min value
# push a tmp min value to the minStack each time when pushing a value into the stack
【时间复杂度】
# O(1) in time for push, pop, minEle
【空间复杂度】
# O(n) in space
【gist link】
https://gist.github.com/zhangjiang2013/9dd06435151670a2f954
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-21 15:04:37 | 显示全部楼层
JamesJi 发表于 2015-4-15 22:16
[解题思路]
额外建立一个stack用来保存每一次push元素进入一个stack时候,此时的min值,这样子就可以完成O ...

应该是s2.peek(), 我也有个疑惑,pop的返回类型如果是int的话在eclipse里面会显示错误,要改成Integer是为什么
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-21 21:12:38 | 显示全部楼层
daphne_ying 发表于 2015-4-21 02:04
应该是s2.peek(), 我也有个疑惑,pop的返回类型如果是int的话在eclipse里面会显示错误,要改成Integer是 ...

对·应该是peek。针对你的问题,因为你定义stack是stack<Integer>,所以返回int是不对的,应该也是要对应的integer
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-24 04:32:03 | 显示全部楼层
【解题思路】
新增一个min值,每次push前检查新数据是否是最小值,替换,我的解法有问题的是pop不一定一直是O(1), 如果pop出了最小值,就得遍历重找最小值
【时间复杂度】
push O(1)
pop worst case: O(n)
min O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... e-3-2-stackmin-java
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-27 12:04:02 | 显示全部楼层
[solution]
use an additional stack to keep track of the min elements.
when pushing x, if the min stack is empty or x is less than or equal to the top of the min stack, push x to the min stack too
when popping x, if x is equal to the top of the min stack, pop the min stack too.
[time]
O(1)
[space]
O(n)
[gist link]
https://gist.github.com/kelly-us/4151fd5c56e2cb9090cb
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-6-3 10:26:25 | 显示全部楼层
【解题思路】use an additonal stack to store the minumum value information.
        Each time pushing a new value, check if the new value is smaller or equal to
        the current minimum value;
        Each time poping the top value, check if the poped value is the minimum value
【时间复杂度】O(1)
【空间复杂度】O(n) in worst case, O(1) in best case
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_2.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 00:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表