【leetcode】MinStack--python版

2019-11-14 17:30:01

字體：大中小

來源：轉載

供稿：網友

題目描述：

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

 1 class MinStack: 2     def __init__(self): 3         self.stack = [] 4         self.minStack = [] 5     # @param x, an integer 6     # @return an integer 7     def push(self, x): 8         self.stack.append(x) 9         if len(self.minStack) == 0 or self.minStack[-1] >= x:10             #11             self.minStack.append(x)12  13     # @return nothing14     def pop(self):15         p = self.stack.pop()16         #print 'pop ' , p17         if p == self.minStack[-1]:18             #print 'minn pop'19             self.minStack.pop()20 21     # @return an integer22     def top(self):23         return self.stack[-1]24 25     # @return an integer26     def getMin(self):27         return self.minStack[-1]

 1 class MinStack: 2     def __init__(self): 3         self.stack = [] 4         self.minStack = [] 5         #self.minStack.append(0) 6     # @param x, an integer 7     # @return an integer 8     def push(self, x): 9         self.stack.append(x)10         if len(self.minStack) == 0 or self.minStack[-1][0] > x:11             #print 'minn change'12             self.minStack.append((x,1))13         elif x == self.minStack[-1][0]:14             self.minStack[-1] = (x, self.minStack[-1][1] + 1)15  16     # @return nothing17     def pop(self):18         p = self.stack.pop()19         #print 'pop ' , p20         if p == self.minStack[-1][0]:21             if self.minStack[-1][1] > 1:22                 #print 'minn pop'23                 self.minStack[-1] = (self.minStack[-1][0], self.minStack[-1][1] - 1)24             else:25                 self.minStack.pop()26 27     # @return an integer28     def top(self):29         return self.stack[-1]30 31     # @return an integer32     def getMin(self):33         #print self.minStack34         return self.minStack[-1][0]