题目描述：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.
解题思路：这个问题挺简单（确实leetcode给的评级也是easy），但是还真是遇上了不少的问题。
首先，这道题目我们的想法是如何去做到这个特殊的getMin，想到的方法当然是空间换时间啦，那么用什么空间呢？当然是另一个栈啦，所以我们就有了这么一个想法：用另一个栈来记录当前最小值，那么查找最小值就不需要遍历了，这样就实现了时间复杂度和空间复杂度都是O(n)。的确这个想法已经很不错了，用java（官方题解就是这个版本）和C++（亲测）。但是我用python就MLE了，让我纠结了好久。
所以在没办法就要优化内存了，这里采用的方法是在minStack中插值的时候对相同的值不重复插入，而是记录他的次数，终于AC
MLE
1classMinStack:2def__init__(self):3self.stack =[]4self.minStack =[]5#@param x, an integer6#@return an integer7defpush(self, x):8self.stack.append(x)9iflen(self.minStack) == 0orself.minStack[-1] >=x:10#PRint 'minn change'11self.minStack.append(x)1213#@return nothing14defpop(self):15p =self.stack.pop()16#print 'pop ' , p17ifp == self.minStack[-1]:18#print 'minn pop'19self.minStack.pop()2021#@return an integer22deftop(self):23returnself.stack[-1]2425#@return an integer26defgetMin(self):27returnself.minStack[-1]
AC
1classMinStack:2def__init__(self):3self.stack =[]4self.minStack =[]5#self.minStack.append(0)6#@param x, an integer7#@return an integer8defpush(self, x):9self.stack.append(x)10iflen(self.minStack) == 0orself.minStack[-1][0] >x:11#print 'minn change'12self.minStack.append((x,1))13elifx == self.minStack[-1][0]:14self.minStack[-1] = (x, self.minStack[-1][1] + 1)1516#@return nothing17defpop(self):18p =self.stack.pop()19#print 'pop ' , p20ifp == self.minStack[-1][0]:21ifself.minStack[-1][1] > 1:22#print 'minn pop'23self.minStack[-1] = (self.minStack[-1][0], self.minStack[-1][1] - 1)24else:25self.minStack.pop()2627#@return an integer28deftop(self):29returnself.stack[-1]3031#@return an integer32defgetMin(self):33#print self.minStack34returnself.minStack[-1][0]