[LeetCode] 155. Min Stack

本文主要是介绍[LeetCode] 155. Min Stack，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目内容

https://leetcode-cn.com/problems/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.

---

题目思路

这道题的考点在于建立一个最小栈来获取每次的最小值。换句话说，我们可以建立一个动态规划的最小栈。用来记录当存入元素i时的最小元素是多少。也就是当一个新的元素入栈时，如果最小栈为空则把这个元素放入最小栈，否则将把这个元素和最小栈元素最小值进行比较后，选择更小的那个放入栈中。

---

程序代码

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.stack=[]self.min_stack=[]def push(self, x):""":type x: int:rtype: None"""self.stack.append(x)if not self.min_stack:self.min_stack.append(x)else:self.min_stack.append(min(self.min_stack[-1],x))def pop(self):""":rtype: None"""tmp=self.stack.pop()self.min_stack.pop()def top(self):""":rtype: int"""return self.stack[-1]def getMin(self):""":rtype: int"""return self.min_stack[-1]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

 

这篇关于[LeetCode] 155. Min Stack的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---