实现一个栈，要求支持push、pop、top和getMin操作，且getMin操作的时间复杂度为O(1)。

Question

Accepted Answer

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

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

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

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

def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]

在这段代码中，self.stack用于存储正常的元素，self.min_stack用于存储当前栈中的最小元素。push操作时，如果新元素小于等于最小栈的栈顶元素，则将其压入最小栈；pop操作时，如果栈顶元素等于最小栈的栈顶元素，则将最小栈的栈顶元素弹出。top操作直接返回栈顶元素，getMin操作直接返回最小栈的栈顶元素，时间复杂度都是$O(1)$。