一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.30-7.6 CareerCup 3.2

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-29 21:15:05 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去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】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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





readman 发表于 2014-6-29 23:49:18 | 显示全部楼层
【解题思路】
new class
【时间复杂度】
【空间复杂度】
【gist link】
https://gist.github.com/gaoyike/4c080dee0aefb287b899
【test case】
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-30 11:24:09 | 显示全部楼层
本帖最后由 grassgigi 于 2014-6-30 11:25 编辑

【解题思路
For each node in stack, keep the min value that under this node in stack. we can achieve this by setting the min value to be min(oldMin, new value) when pushing the element into stack.

【时间复杂度】
O(1)

【空间复杂度】
O(N) - for each element node, we add one more field(possibly 32 bit integer) to track the min value under this node

【gist link】
https://gist.github.com/chrislukkk/384d682e551e1d2708b7
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-30 12:25:25 | 显示全部楼层
【解题思路】
使用一个额外的Stack——minStack,用来存储所有最小值(即原Stack中有1个元素、2个元素、。。。、N个元素时对应的N个最小值)。
每次pop原Stack时,也同时pop minStack,反之push新元素进Stack时,也需要更新最小值,并将更新过后的最小值push进minStack。
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/chouclee/558ad32946d86acc14c6
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-1 04:03:37 | 显示全部楼层
【解题思路】
push自带记录最小值功能,也就是说push不再是一个void而是int,return最小值。min则自然就是return this.push()
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://github.com/donnice/donnice/blob/master/Q3_2

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-2 01:36:41 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-7-2 08:19:09 | 显示全部楼层
【解题思路】
idea: use another stack to store current minimum value each time a new element is pushed in.
       pop top values from both 2 stacks when doing pop operation
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/monkerek/e1d5656ee37ec8616b63
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-7-2 10:09:22 | 显示全部楼层
【解题思路
Use an extra stack to store the elements who were ever a min, if the current min is being poped, pop it out of the extra min stack as well.
【时间复杂度】
【空间复杂度】
O(N)

【gist link】
https://gist.github.com/XiaoxiaoLi/fc9358f27dd4d0983b45
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-7-2 11:06:45 | 显示全部楼层
【解题思路】
METHOD 1: we can store current min value in the top node. When we push(), we compare the inserted value and the min value in the top node, and store the new min value in the inserted node. When we pop(), we don't need to do anything.
METHOD 2:  method 1 store too many duplicate min value. Instead, we can create a new stack to store min value, when the min value change, we push and pop the new stack.
【时间复杂度】
1. O(1)
2. O(1)
【空间复杂度】
1. theta(n)
2. O(n)
【gist link】
https://gist.github.com/qianhuang/d3372229c258943bcee5
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-2 23:58:59 | 显示全部楼层
【解题思路】Use an extra stack to store the elements who is currently minimum.
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】https://gist.github.com/bitcpf/1bb37f98c1c8ee17b0e2
回复 支持 反对

使用道具 举报

pud 发表于 2014-7-3 05:49:46 | 显示全部楼层
【解题思路】
create another stack to record the minimum element in the stack for every push.  pop both stacks.
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/yokiy/7ab19f4b78de60a32eb5
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-3 06:51:09 | 显示全部楼层
【解题思路】
use an extra stack to store the min values.  push an element to the extra stack if the min changes;  Also pop the min value from the extra stack when it is popped from the primary stack;
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】 https://gist.github.com/jyhjuzi/60c4cad863717bff7e04
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-3 11:03:29 | 显示全部楼层
【解题思路】Use another stack to keep min values
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/nealhu/9fd25a583db13d4e7647
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-3 11:13:25 | 显示全部楼层
【解题思路】
construct a new class to extend the class Stack with an inner Stack to record the mins
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/9fdc6b744d63b0238b3a
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-5 05:47:36 | 显示全部楼层
【解题思路】
use an extra array to track the min, but only push the val to this array if the val is smaller than the current min. when pop, if the value is equal to the current min, then update the min.
【时间复杂度】
Amortized O(1) for push and O(1) for pop and min
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/5c62763ac77541d24e28
回复 支持 反对

使用道具 举报

nickmyself 发表于 2014-7-5 06:11:01 | 显示全部楼层
【解题思路】
Keep 2 stacks, one for original element, one for min element.
【时间复杂度】
pop(),push(),min()均为 O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/nickmyself/1af9ebe0ed35c6a8f843
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-6 08:58:14 | 显示全部楼层
【解题思路】User another stack to store the current min.
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/60751e16fd55a162bf8b
回复 支持 反对

使用道具 举报

tangcx18 发表于 2014-7-6 09:56:21 | 显示全部楼层
【解题思路】construct a vector to store data and a minStack to store min
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/f973c01175c5093102e9
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-7 00:58:16 | 显示全部楼层
【解题思路】
use an extra stack (let's call it minValue) to hold every new minimum, min() returns minValue.top().
push into minValue when new data is smaller than or equal to current minimum
pop from minValue if the popped-out value was current minimum
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/734e0c5815394b7d1313
【test case】
Example in the solution:
input: 5->6->3->7->pop->pop
output: 5, 5, 3, 3, 3, 5
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-7 03:03:21 | 显示全部楼层
【解题思路】
use 1 int single value(min value) as a menber of the stack.When minvalue is poped from the stack, update.
【时间复杂度】
o(1)
【空间复杂度】
o(n)
【gist link】https://gist.github.com/hilda8519/7963ed7fe23fdc513dfd
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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