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.
Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); –> Returns -3. minStack.pop(); minStack.top(); –> Returns 0. minStack.getMin(); –> Returns -2.
思路： 用列表实现栈的思想，先进后出 push():直接在列表尾部加元素即可 pop():从尾部找元素出栈 top():直接获取尾部的元素 getMin():获取列表最小元素 这样做可能不满足题目要求，对时间的限制
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.l = []
print(self.l)
def __str__(self):
msg = "目前的列表为" + str(self.l)
return msg
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.l.append(x)
def pop(self):
"""
:rtype: void
"""
self.l.pop()
def top(self):
"""
:rtype: int
"""
return self.l[len(self.l) - 1]
def getMin(self):
"""
:rtype: int
"""
return min(self.l)
if __name__ == "__main__":
# Your MinStack object will be instantiated and called as such:
obj = MinStack()
print(str(obj))
obj.push(1)
obj.push(2)
obj.push(-8)
obj.push(-2)
obj.push(-9)
print(str(obj))
#obj.pop()
param_3 = obj.top()
param_4 = obj.getMin()
print("栈顶部的元素为：" + str(param_3))
print("栈中最小值为：" + str(param_4))
print(obj.getMin())
obj.pop()
print(obj.getMin())
此代码有问题
网上思路：http://bookshadow.com/weblog/2014/11/10/leetcode-min-stack/
需要定义两个栈
class MinStack:
# @param x, an integer
# @return an integer
def __init__(self):
self.stack = []
self.minStack = [] #最小值栈
def push(self, x):
self.stack.append(x)
#如果 最小值栈为空，或者新增值 <= 最小值栈顶的值
if len(self.minStack) == 0 or x <= self.minStack[-1]:
#x入最小值栈
self.minStack.append(x)
def pop(self):
#如果 栈顶值 == 最小值栈顶值
if self.top() == self.getMin():
#最小值栈顶元素弹出
self.minStack.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.minStack[-1]
