俄罗斯套娃信封:回溯输出所有嵌套路径
哪些公司问过
答案要点
- 宽高都必须严格大于才能嵌套,信封不能旋转
- 求最大层数:宽升序、同宽高降序后,对高度求最长严格递增子序列
- 贪心加二分求长度为O(n log n)
- 输出所有路径用排序后DFS回溯,加入、递归、撤销
- 用DP预处理最长链长度做剪枝,路径数可能是指数级
易错点
- 同宽时按高升序,导致同宽信封被错误嵌套
- 只比较宽或用大于等于,违反严格嵌套
- 以为二分LIS的tails数组就是实际路径
面试官常见追问
- 为什么宽相同时要按高降序?
- 如果只要输出一条最长路径呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。