面试题库 › 客户端 › 验证栈的压入弹出序列是否合法(LC946)

验证栈的压入弹出序列是否合法(LC946)

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

哪些公司问过

字节跳动2

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

答案要点

  1. 用辅助栈按 push 序列依次入栈
  2. 每次入栈后,循环比较栈顶与 pop 序列当前元素,相等则弹出并后移指针
  3. 全部入栈后栈为空则合法,否则不合法
  4. 贪心正确性:元素互不相同时,栈顶能匹配就立即弹出不会错
  5. 时间 O(n),空间 O(n);注意长度不等和空序列边界

易错点

面试官常见追问

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

相关面试题