LeetCode#155 Min Stack

Problem Definition:

　　Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Sulotion 1：一个附加栈来存储最小值。只存储那些新的最小值；每次pop都要检查，如果出栈元素与附加栈栈顶元素相同，附加栈也pop。

 1 class MinStack:
 2     
 3     def __init__(self):
 4         self.nums=[]
 5         self.min=[sys.maxint]
 6   
 7     def push(self, x):
 8         self.nums+=x,    #一点小trick，x转成tuple,相当于append(x)
 9         if x<=self.min[len(self.min)-1]:#注意，重复的min也要进栈
10             self.min+=x,
11      
12     def pop(self):
13         p=self.nums.pop()
14         if p==self.min[len(self.min)-1]:
15             self.min.pop()
16 
17     def top(self):
18         return self.nums[len(self.nums)-1]
19 
20     def getMin(self):
21         return self.min[len(self.min)-1]

这种以空间-时间tradeoff的方法很普通，下面来看一种酷炫的实现，常数空间复杂度：

Solution 2:

 1 class MinStack:
 2 
 3     def __init__(self):
 4         self.min = sys.maxint
 5         self.diffs = []
 6 
 7     def push(self, x):
 8         self.diffs += x - self.min,
 9         self.min = min(self.min, x)
10 
11     def pop(self):
12         diff = self.diffs.pop()
13         self.min -= min(diff, 0)
14 
15     def top(self):
16         return self.min + max(self.diffs[-1], 0)
17 
18     def getMin(self):
19         return self.min

Now let's see the tricks here:

1）diffs数组里保存的是元素进栈时与当时的最小值的差，这个差可能为正可能为负；min记录的则是当前的最小值。

2）push：将上述差值 x-min 入栈，如果压入的数大于等于0，则min保持不变，否则令 min=x为新的最小值。

3）pop ：首先会把栈顶元素删除。然后考虑是否要改变min：

　　　 1._如果栈顶元素是非负的，说明这个元素入栈时不小于当时的min，因此这个元素入栈时没有改变（更新）min，因此删除它的时候也就无需改变（恢复）min，即执行min-=0；

　　　 2._如果栈顶元素是负数，说明这个元素入栈时小于当时的min，因此这个元素入栈时更新了min，因此删除它的时候要恢复min，即执行min-=diff；

4）top： 1._如果栈顶元素是非负的，说明这个元素入栈时不小于当时的min，因此它的入栈没有改变min，因此返回min+diffs[-1]

　　　 2._如果栈顶元素是负的，则这个元素入栈时更新了min，而min存储的正是这个元素入栈时的值，因此返回min。