设计包含min函数的栈 ？

在计算机科学中，栈（Stack）是一种特殊的线性数据结构，它遵循后进先出（LIFO）的原则。这意味着最后一个被添加到栈中的元素将是第一个被移除的。栈通常用于存储函数调用、数据处理等场景。

为了设计一个包含min函数的栈，我们需要在普通的栈的基础上增加一些额外的数据结构来跟踪栈中的最小值。以下是一种可能的实现方式：

class MinStack:
    def __init__(self):
        self.stack = []  # 用于存储栈中的元素
        self.min_stack = []  # 用于存储栈中的最小值

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:  # 如果x小于等于当前最小值，则将其添加到min_stack中
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:  # 如果弹出的元素是当前最小值，则min_stack也需要弹出
                self.min_stack.pop()
            return 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]  # min_stack的栈顶元素即为当前栈的最小值

这个实现中，我们使用了两个栈：stack和min_stack。stack用于存储所有元素，遵循LIFO原则。min_stack则用于存储当前栈中的最小值。在每次push操作中，我们都会检查新元素是否小于等于当前最小值，如果是，则将其添加到min_stack中。在每次pop操作中，我们都会检查弹出的元素是否是当前最小值，如果是，则将min_stack的栈顶元素也弹出。这样，min_stack的栈顶元素就始终是stack中的当前最小值。因此，getMin操作的时间复杂度为O(1)。