← 返回编程题库
coding-min-stack-with-getmin简单免费版2000ms未尝试

支持 O(1) 取最小值的最小栈

Min-Stack with O(1) get_min

开始编码

你在为 tick 流监控搭一个小型遥测原语:行情进来时,团队希望维护一个最近样本窗口,并能在 O(1) 内回答「当前窗口里的最小值是多少?」——比如某个会话标记之后见到的最低买价、或最近 N 条样本里的最小延迟。经典做法是一个最小栈:栈结构 + pushpoptopget_min 都是 O(1) 摊还。

请实现 solution(events: list[dict]) -> listevents 中每一项是四种操作之一:{"type": "push", "value": v}{"type": "pop"}{"type": "top"}{"type": "get_min"}。把事件依次作用到一个初始为空的栈上,按输入顺序返回每个事件的响应:push 没有返回值(用 None),pop 返回弹出的整数,top 返回当前栈顶整数,get_min 返回当前最小值。对空栈调用 poptopget_min 必须抛出 ValueError。事件列表为空时返回 []

示例 1events = [{"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示例 2events = [{"type": "push", "value": 5}, {"type": "get_min"}] 返回 [None, 5]——栈里只有一个元素,它本身就是最小值。示例 3events = [] 返回 []——没有事件,自然也没有响应。

朴素的做法是 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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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 的经典样例。