面试题库 › Java 后端 › 实现支持 O(1) 获取最小值的栈

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

难度 ★★☆在 9 场真实面经中被问到 方向:Java 后端考点:栈与队列

哪些公司问过

美团2字节跳动2腾讯1地平线1滴滴1拼多多1深势科技1

常见岗位:Java 后端、C/C++ 软件开发、C++ / Qt 客户端、iOS

答案要点

  1. 辅助栈与主栈同步,记录每一时刻的最小值
  2. push:辅助栈压入 min(新值, 辅助栈顶);pop:两个栈同时弹出
  3. getMin:返回辅助栈的栈顶,O(1);空间 O(n)
  4. 优化:辅助栈只在新值 ≤ 当前最小值时才压入,弹出的值等于辅助栈顶时才弹出,需用 ≤ 处理重复最小值
  5. 也可以栈中存与最小值的差值,再用一个变量记录最小值

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题