【第四轮】4.13 - 4.19 Career Cup 3.2

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、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

[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

[解题思路]
额外建立一个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】

【解题思路】
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

【解题思路】
# 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

JamesJi 发表于 2015-4-15 22:16
[解题思路]
额外建立一个stack用来保存每一次push元素进入一个stack时候，此时的min值，这样子就可以完成O ...

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

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

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

【解题思路】
新增一个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

[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

【解题思路】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，如果觉得比较好，欢迎贴出来分享）