[第二轮] 3/4-3/10 CareerCup 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.


发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

my first thought is having a variable cur_min within each node，function min is the top.().cur_min. And compare the min() to maintain the min in the stack before every time push a new node...

Add min attribute for every stack element, which trace the minimum value for all nodes below itself.
Key point here is the minimum value below one node will not change during its life time.
https://gist.github.com/chrislukkk/5078590

https://gist.github.com/mettaworld/5081901
java language
use linked list to make a stack and and get the least data in this stack with a loop.....

https://github.com/longwei/Algo/ ... 3/StackWithMin.java

another way to think about it.
The most difficult part is to peek the min ops in constant time.
1. same the above, add a min attribut to stack, so each element in stack remember the min element.2. use additonal stack to tracking the min element.

JAVA
初始化Stack的时候，总是把所有元素都初始化成 “0”。
为了避免排序的时候出错，在min方法里得把Stack里得有效元素抽出来。

https://gist.github.com/lazyGoose/5087021

Solution1: for each element, we also store the min value of all the elements in current stack

C++ implementation

https://github.com/StanleyLee/CareerCup/blob/master/3_2.cpp

自己没有想到第二种算法，用另外一个stack来track min值，实现是应该注意push、pop操作 ：）

用两个stack的方法实现了一遍，方法的思想如下：
用valueStack来存储正常的数据，每次push值入valueStack时，比较当前值与另一个minStack的第一个元素比较，如果小于等于minStack的第一个元素，则push入minStack；当pop时，如果pop的元素和minStack的第一元素相等，则minStack也pop出此元素。

C++ implementation

https://github.com/StanleyLee/CareerCup/blob/master/3_2_1.cpp

https://gist.github.com/ThunderXu/5122243
Use a LinkedList to realize, each node has attributes "data", "next" and "min", for those nodes who has the minimal element when it is at the top of the stack, its "min" sttribute points to the minimal node when it hasn't been pushed, then if the current mininal node is poped, just set the minimal node to the node it's "min" pointer points to.

https://github.com/quantumrose/C ... 2.StackWithMin.java