【第三轮】6.30-7.6 CareerCup 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】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

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

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

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

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

【解题思路】
new class
【时间复杂度】
【空间复杂度】
【gist link】
https://gist.github.com/gaoyike/4c080dee0aefb287b899
【test case】

【解题思路】
使用一个额外的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

【解题思路】
push自带记录最小值功能，也就是说push不再是一个void而是int，return最小值。min则自然就是return this.push()
【时间复杂度】
O(1)
【空间复杂度】
O(n)
【gist link】
https://github.com/donnice/donnice/blob/master/Q3_2

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

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

【解题思路】Use an extra stack to store the elements who is currently minimum.
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】https://gist.github.com/bitcpf/1bb37f98c1c8ee17b0e2