IT 面试题库

场景题:你要为一个行情系统设计一个「最小栈」(LeetCode 155),除 push/pop/top 外还要 O(1) 返回当前栈内最小值 getMin。常规栈为什么做不到?请给出设计并说明每个辅助栈元素的生命周期。

中级场景题算法工程师Java后端工程师栈设计最小栈LeetCode155空间换时间

题目

考察点:用空间换时间的设计思维——辅助栈与主栈的同步关系。追问:只用一个变量记录最小值,pop 之后会出什么问题?

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:配一个同步维护的辅助栈,栈顶永远保存「当前主栈全部元素的最小值」。

- 主栈正常存数据;

- 辅助栈在 push 时压入 min(x, 辅助栈栈顶)(辅助栈为空时直接压 x);pop 时两栈同时弹出。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题