【第三轮】6.30-7.6 CareerCup 3.2

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

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

【解题思路】Use another stack to keep min values
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/nealhu/9fd25a583db13d4e7647

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

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

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

【解题思路】User another stack to store the current min.
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/60751e16fd55a162bf8b

【解题思路】construct a vector to store data and a minStack to store min
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/f973c01175c5093102e9

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

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