首页 > 代码库 > Min Stack
Min Stack
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.
分析：
要求实现一个栈，支持O(1)时间的取最小元素操作。
我用了很简单的办法来做，导致pop()的时间复杂度为O(n)，应该有更好的方式，但是我没有想到时间少于O(logN)的解决方案，先提交代码也Accepted了。
class MinStack: # @param x, an integer # @return an integer def __init__(self): self.stack = [] self.min = None def push(self, x): if not self.min or x < self.min: self.min = x self.stack.append(x) # @return nothing def pop(self): i = self.stack.pop() if len(self.stack) == 0: self.min = None elif i == self.min: self.min = min(self.stack) # @return an integer def top(self): return self.stack[-1] # @return an integer def getMin(self): return self.min
小结：
leetcode上有关于这个问题的解答，需要考虑一下才能明白，下面代码所有操作的时间复杂度都是O(1)：
class MinStack: # @param x, an integer # @return an integer def __init__(self): self.stack = [] self.min = [] def push(self, x): self.stack.append(x) if len(self.min) == 0 or x <= self.min[-1]: self.min.append(x) # @return nothing def pop(self): if len(self.stack) > 0: if self.stack.pop() == self.min[-1]: self.min.pop() # @return an integer def top(self): return self.stack[-1] # @return an integer def getMin(self): return self.min[-1]
在算法的思考方面我还需要磨练，多做题是个不错的锻炼方式，有进步就好。但是最近工作很忙，要学习的框架和技术很多，实在没有多余的精力来阅读和写作。鱼与熊掌不可兼得。
Min Stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。