请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。简单但经典

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

思路：

可以用两个栈来模拟这一个栈的功能。其中一个栈使用正常栈，另外一个栈来存储当前的最小值。

举个例子如果入栈的元素是 2 3 1 4 7 -1，入栈后如图

代码如下

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.stack=[]self.minstack=[]self.minstack.append(2147483647)def push(self, x):""":type x: int:rtype: None"""self.stack.append(x)self.minstack.append(min(self.minstack[-1],x))def pop(self):""":rtype: None"""self.stack.pop()self.minstack.pop()def top(self):""":rtype: int"""return self.stack[-1]def getMin(self):""":rtype: int"""return self.minstack[-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()

 

1. 时间复杂度：

   • push、pop、top和getMin操作的时间复杂度均为 ，因为这些操作都是基于列表的基本操作，时间复杂度与栈的大小无关。

2. 空间复杂度：

   • 空间复杂度取决于存储在栈中的元素数量。在最坏的情况下，主栈和辅助栈都需要存储所有的元素，因此空间复杂度为 ，其中 n 是栈中的元素数量。