22067: 快速堆猪

辅助栈, http://cs101.openjudge.cn/practice/22067/

题解在

https://github.com/GMyhf/2024spring-cs201/blob/main/2024spring_dsa_problems.md

这题目用不到单调栈。单调栈的定义：单调栈是一种特殊的栈结构，其内的元素按照某种顺序（如递增或递减）排列。当新元素入栈时，会将栈内所有不符合这种顺序的元素弹出，以保证栈内的元素始终满足所设定的顺序。单调栈通常用于解决某些特定的问题，比如下一个更大元素问题、直方图中最大的矩形等。

可以创建两个栈：一个用于存储所有的元素，另一个用于追踪最小值。当向主栈中 push 元素时，同时检查是否需要更新最小值栈；当从主栈中 pop 元素时，也检查是否需要从最小值栈中移除相应的最小值。

python

class MinStack:
    def __init__(self):
        self.stack = []          # 主栈
        self.min_stack = []      # 辅助栈，用来保存每个状态下的最小值

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

    def pop(self):
        if self.stack:  # 如果主栈非空才执行pop
            top = self.stack.pop()
            if top == self.min_stack[-1]:
                self.min_stack.pop()

    def min(self):
        if self.min_stack:
            return self.min_stack[-1]
        else:
            return None  # 栈为空时返回None

# 使用 MinStack 类
min_stack = MinStack()

while True:
    try:
        command = input().strip()
        if command.startswith('push'):
            value = int(command.split()[1])
            min_stack.push(value)
        elif command.startswith('pop'):
            min_stack.pop()  # 空栈时不进行任何操作
        elif command.startswith('min'):
            min_value = min_stack.min()
            if min_value is not None:
                print(min_value)  # 只有在栈非空时才打印最小值
    except EOFError:
        break

这段代码实现了更健壮的最小值追踪机制，确保即使有多个相同的最小值被连续添加和移除，也能正确地保持最小值信息。

22067: 快速堆猪 ​

22067: 快速堆猪