实现一个栈，要求支持push、pop、top和获取最小元素的操作，且这些操作的时间复杂度都为O(1)。

Question

Accepted Answer

为了实现一个支持push、pop、top和获取最小元素操作且时间复杂度都为O(1)的栈，我们可以使用两个栈。一个栈用于存储正常的元素，另一个栈用于存储当前栈中的最小元素。以下是Python代码实现：
python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

def pop(self):
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()

def top(self):
        if self.stack:
            return self.stack[-1]

def getMin(self):
        if self.min_stack:
            return self.min_stack[-1]
在这个实现中，`push`操作时，除了将元素添加到`stack`中，还会检查该元素是否小于等于`min_stack`的栈顶元素，如果是则将其添加到`min_stack`中。`pop`操作时，如果`stack`的栈顶元素等于`min_stack`的栈顶元素，则同时从两个栈中弹出元素。`top`操作直接返回`stack`的栈顶元素，`getMin`操作直接返回`min_stack`的栈顶元素。这样可以保证每个操作的时间复杂度都是O(1)。