支持 O(1) 取最小值的最小栈
Min-Stack with O(1) get_min
开始编码你在为 tick 流监控搭一个小型遥测原语:行情进来时,团队希望维护一个最近样本窗口,并能在 O(1) 内回答「当前窗口里的最小值是多少?」——比如某个会话标记之后见到的最低买价、或最近 N 条样本里的最小延迟。经典做法是一个最小栈:栈结构 + push、pop、top、get_min 都是 O(1) 摊还。
请实现 solution(events: list[dict]) -> list。events 中每一项是四种操作之一:{"type": "push", "value": v}、{"type": "pop"}、{"type": "top"}、{"type": "get_min"}。把事件依次作用到一个初始为空的栈上,按输入顺序返回每个事件的响应:push 没有返回值(用 None),pop 返回弹出的整数,top 返回当前栈顶整数,get_min 返回当前最小值。对空栈调用 pop、top、get_min 必须抛出 ValueError。事件列表为空时返回 []。
示例 1:events = [{"type": "push", "value": -2}, {"type": "push", "value": 0}, {"type": "push", "value": -3}, {"type": "get_min"}, {"type": "pop"}, {"type": "top"}, {"type": "get_min"}] 应返回 [None, None, None, -3, -3, 0, -2]。三次 push 之后栈为 [-2, 0, -3](右侧为栈顶),当前最小值是 -3;pop 弹出 -3 后栈变为 [-2, 0],栈顶是 0,最小值「回退」到 -2。示例 2:events = [{"type": "push", "value": 5}, {"type": "get_min"}] 返回 [None, 5]——栈里只有一个元素,它本身就是最小值。示例 3:events = [] 返回 []——没有事件,自然也没有响应。
朴素的做法是 get_min 时扫一遍栈:每次查询 O(n),查询频繁时就吃不消。教科书级单调栈应用的经典技巧是:维护一个与主栈同步的辅助最小栈,每次 push 时追加 min(新值, 当前最小值)、每次 pop 时两边一起弹。这样 get_min 只需读辅助栈栈顶——O(1),不用扫描、不用重建。脑子里要守住的不变量:每次操作完之后,min_stack[-1] 等于主栈当前所有元素的最小值,且两栈长度始终一致。
约束条件
- 0 ≤ 事件数 ≤ 10⁴
- push 事件的 `value` 字段为整数(可正、可负、可零)
- 对空栈调用 pop / top / get_min 必须抛出 `ValueError`
- `event['type']` 取值为 `'push'`、`'pop'`、`'top'`、`'get_min'` 之一
- 输出是一个列表,每个事件对应一项,按输入顺序:push → None;pop → 弹出值;top → 栈顶值;get_min → 当前最小值
样例
Case 1 · empty event list
输入: [[]]
期望: []
事件列表为空时,没有任何操作发生,直接返回空列表。
Case 2 · push then get_min returns the pushed value
输入: [[{"type":"push","value":5},{"type":"get_min"}]]
期望: [null,5]
push 5 后栈中只有 5,最小值就是 5。push 事件无返回值(None),get_min 返回当前最小值 5。
Case 3 · classic LeetCode 155 trace
输入: [[{"type":"push","value":-2},{"type":"push","value":0},{"type":"push","value":-3},{"type":"get_min"},{"type":"pop"},{"type":"top"},{"type":"get_min"}]]
期望: [null,null,null,-3,-3,0,-2]
依次 push -2、0、-3 后 get_min=-3;pop 弹出 -3 后栈顶是 0、最小值回退到 -2。这是 LeetCode 155 的经典样例。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · empty event list
输入: [[]]
期望: []
事件列表为空时,没有任何操作发生,直接返回空列表。
Case 2 · push then get_min returns the pushed value
输入: [[{"type":"push","value":5},{"type":"get_min"}]]
期望: [null,5]
push 5 后栈中只有 5,最小值就是 5。push 事件无返回值(None),get_min 返回当前最小值 5。
Case 3 · classic LeetCode 155 trace
输入: [[{"type":"push","value":-2},{"type":"push","value":0},{"type":"push","value":-3},{"type":"get_min"},{"type":"pop"},{"type":"top"},{"type":"get_min"}]]
期望: [null,null,null,-3,-3,0,-2]
依次 push -2、0、-3 后 get_min=-3;pop 弹出 -3 后栈顶是 0、最小值回退到 -2。这是 LeetCode 155 的经典样例。