面试题库 › Java 后端 › 求给定入栈顺序的所有出栈序列

求给定入栈顺序的所有出栈序列

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

哪些公司问过

微软1

常见岗位:Java 后端

答案要点

  1. 回溯两种选择:有剩余元素就入栈,栈非空就出栈,递归返回后撤销
  2. 所有元素都入过栈且栈空时,记录一个完整出栈序列
  3. 序列总数为卡特兰数C(2n,n)/(n+1),n=3时为5种,312不合法
  4. 判断单个序列是否合法可用辅助栈模拟,时间O(n)
  5. 入栈元素有重复时需对结果去重

易错点

面试官常见追问

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

相关面试题