- 正确答案：这是一个经典的“嵌套矩形”或“嵌套箱子”问题（Box Stacking 的简化变种），题目约束为“只能从前往后嵌套”，即给定一个箱子序列（每个箱子用长宽高表示，或简化为二维如长宽），要求选出最长的子序列，使得每个箱子能严格放入前一个箱子中（即当前箱子的长 < 前一箱子的长，且宽 < 前一箱子的宽）；注意：此处“从前往后”意味着**子序列必须保持原始顺序（不可重排）**，因此不是一般 Box Stacking（可重排+旋转），而是“带顺序约束的最长递增子序列（LIS）二维推广”——即最长嵌套子序列（Longest Nesting Subsequence, LNS），可用回溯（暴力枚举所有合法子序列）求解，时间复杂度 O(2^n)，适用于小规模 n（如 n ≤ 20）；更优解法是动态规划 O(n²)，但题目明确要求“回溯解决”，故需实现状态空间搜索+剪枝。 - 解答思路： 1. 明确嵌套条件：箱子 i 能放入箱子 j（j 在 i 前面，即 j < i）当且仅当 box[i].length < box[j].length 且 box[i].width < box[j].width（若三维则还需 height < height；本题未指定维度，默认二维简化；若为三维，同理扩展比较条件）。 2. 回溯设计：定义 dfs(pos, last_idx) 表示从索引 pos 开始，上一个已选箱子下标为 last_idx（初始为 -1，表示尚未选任何箱子），返回以该状态出发能构成的最大嵌套层数。 3. 每一步决策：对当前位置 pos，有两种选择： - 跳过 box[pos] → dfs(pos + 1, last_idx) - 若 box[pos] 可嵌入 last_idx 对应的箱子（或 last_idx == -1，即作为首层），则选取它 → 1 + dfs(pos + 1, pos) 4. 终止条件：pos == n，返回 0。 5. 为提升效率，加入剪枝：若剩余未考虑箱子数（n - pos） + 当前已选层数 ≤ 当前最优解，则剪枝（可行性剪枝）；也可预处理排序或使用记忆化，但纯回溯通常不记忆化（因状态含 last_idx，维度高，记忆化收益低，且题目强调“回溯”，侧重搜索逻辑）。 - 深度知识讲解：本题本质是组合搜索问题，在约束条件下枚举所有可行子序列。回溯法的核心是“试错+撤销”，其时间复杂度由解空间大小决定：n 个元素的子序列共 2^n 个，而嵌套约束会剪掉部分分支，但最坏仍是指数级。底层知识点包括： • 子序列 vs 子数组：本题要求“从前往后”即子序列（保持顺序，不连续也可），而非子数组（连续），因此需显式维护 last_idx 而非仅起始位置。 • 嵌套的偏序关系：二维嵌套（l,w）定义了一个偏序集（partially ordered set），其中 (l1,w1) > (l2,w2) 当且仅当 l1>l2 且 w1>w2；问题转化为在给定链（chain）中找最长链 —— Dilworth 定理相关，但回溯不依赖此理论。 • 剪枝策略：除基础边界剪枝外，可预计算“从位置 pos 开始，理论上最多还能选多少个箱子”（即 pos 后满足严格递减的最长子序列长度），通过单调栈或预处理 O(n²) 计算，实现乐观估计剪枝（bound pruning），大幅提升实际性能。 • 状态设计关键：last_idx 是必要状态变量，因为嵌套合法性依赖于上一个具体箱子的尺寸，无法仅用“当前最小长/宽”压缩（因后续箱子需同时小于二者，而不同路径的 last_idx 导致约束不同），故状态不可降维，这是回溯比 DP 更难优化的根本原因。 • 对比 DP 解法：DP 状态 dp[i] = 以第 i 个箱子结尾的最长嵌套层数，则 dp[i] = 1 + max{ dp[j] | j < i and box[j] 可嵌套 box[i] }，时间 O(n²)，空间 O(n)；但 DP 不满足“回溯”要求，且无法直接输出方案路径（需额外 parent 数组）。 - 伪代码（回溯实现，含基础剪枝）： ``` function maxNestingBoxes(boxes): n = length(boxes) best = 0 path = [] // 可选：记录当前路径，用于调试或输出方案 function backtrack(pos, last_idx, depth): nonlocal best, path if depth > best: best = depth // 剪枝1：剩余位置不足以超越当前最优 if pos == n: return if depth + (n - pos) <= best: // 乐观估计：剩余每个都选也超不过best return // 选项1：跳过当前箱子 backtrack(pos + 1, last_idx, depth) // 选项2：尝试选取当前箱子 if last_idx == -1 or (boxes[pos].length < boxes[last_idx].length and boxes[pos].width < boxes[last_idx].width): // 可嵌套（或为首层） backtrack(pos + 1, pos, depth + 1) backtrack(0, -1, 0) return best ``` - 扩展说明：若题目允许箱子旋转（如二维箱子可交换长宽），则每个箱子生成多个朝向（二维有2种，三维有6种），需先预处理所有合法朝向并去重，再排序（如按长降序、宽降序）以减少无效比较；但本题未提旋转，故不考虑。若要求输出具体嵌套方案（哪几个箱子），需在 backtrack 中维护 path 列表，进入时 path.append(pos)，退出时 path.pop()。实际校招面试中，面试官可能追问：如何优化？答：改用 DP（O(n²)）；能否到 O(n log n)？答：二维 LIS 无 O(n log n) 精确解（因偏序不可全序化），但若固定一维排序后对另一维求 LIS（需保证第一维严格递减且第二维严格递减），可做到 O(n log n)，前提是预处理排序+去重+坐标离散化+树状数组/线段树维护，但此已超出回溯范畴。注意：本题“最多用多少层”即最大深度，等价于最长嵌套子序列长度，与“最多箱子数”一致（每层一个箱子）。

滴滴一面面经

全站热榜

创作者周榜