大厂OD机考C卷里那道“书籍叠放”是最近被问得比较多的一道题。朋友问我“Java怎么写能拿满分”我第一反应是这不就是二维LIS最长递增子序列换了个壳吗但转念一想刚接触这类题的人确实容易被“长宽高”“可以旋转”“双机位监考不能翻资料”这些乱七八糟的东西绕晕。今天干脆把这道题从读题到手撕代码的完整过程写出来给正在准备大厂OD机考的朋友做个参考。这道题本质上是“排序 动态规划”在笔试里属于性价比很高的模板题。你把它吃透了顺手还能拿下信封嵌套、搭积木、叠箱子这一整类题目。下面我直接用Java代码讲过程中会把每一步为什么这么设计拆开说清楚尤其是“为什么按长度升序、宽度降序排”这种关键点网上很多题解都是一句话带过实际自己写的时候特别容易踩坑。1. 题目理解与考点拆解1.1 这道题到底想考什么题目背景常见描述是有若干本书每本书有长、宽、高三个属性。现在要把书叠成一摞要求上面那本书的长和宽都必须严格小于下面那本书的长和宽每本书可以旋转摆放也就是长和宽可以互换。问最多能叠多高或者最多能叠几本书。先把这个输入输出结构说清楚。有的版本第一行是整数 n表示书上数量后面 n 行每行是“书名 长 宽 高”。有的版本没有书名直接就是“长 宽 高”。不管哪种核心模型都一样给你一堆三维矩形用其中两个维度做叠放约束第三个维度作为价值/高度求满足约束的最优堆叠。很多第一次见这道题的人第一反应是用 DFS 或者贪心。比如有人会想我按面积从小到大排然后逐个试这看起来很像贪心。但面积小不代表长宽一定小一本书面积小但长特别长、宽特别窄它可能放不到另一本面积更大但长宽更均衡的书上面。贪心在这里很容易找到反例所以核心解法绝不是简单排序后选。这道题真正的考点是二维偏序约束下的最长链问题。把“长、宽”看成一个二维坐标点(x1, y1) 能放在 (x2, y2) 上面当且仅当 x1 x2 且 y1 y2。这不就是二维LIS吗一维LIS是一堆数里找最长递增序列二维LIS把约束扩展到了两个维度。理解了这一点整个解题框架就清晰了先排序把一维降下来再做一维DP。1.2 从“信封嵌套”到“书籍叠放”如果你写过经典的信封嵌套问题就会觉得这题特别眼熟。信封嵌套是有一堆信封每个信封有长和宽大信封能套小信封的条件是小信封的长宽都严格小于大信封的长宽问最多能套几层。俄罗斯套娃、套箱子都是同一个模型。“书籍叠放”只是把“数量”升级成了“高度”作为优化目标。换句话说信封嵌套求的是最大嵌套层数书籍叠放求的是最大总高度。你可以把“高度”理解成每个节点的权重从“最长长度”变成“最大权重和”。这个区别在DP状态设计里体现得非常明显后面我会详细讲。所以千万别把这道题当成什么偏题怪题它就是一个套了场景的模板题。你把这题刷明白等于把一整套“二维偏序DP”都刷明白了。这也是为什么很多刷题攻略都建议优先掌握这类题性价比极高。2. 方案选型排序与状态转移怎么设计才不算错2.1 旋转处理为什么要先把长宽归一化题目说书可以旋转长和宽可以互换。这意味着同一本书其实有两种放法。常规做法是统一处理成长边、短边也就是把每本书的长宽调整成 max(a,b) 和 min(a,b)。为什么要这么做因为叠放约束本质上只看“能不能放下”和长边短边的方向无关。如果一本书原始长宽是 (8, 10)它可以旋转成 (10, 8)。另一本书是 (12, 9)原始情况下 8 12 且 10 9 不成立看着放不下但旋转后变成 (10, 8)10 12 且 8 9 就成立了。所以不统一方向直接比较会漏掉可行解。统一成长边 短边之后所有书处在同一套坐标基准下比较逻辑会简单很多。这里也有一个容易忽略的口袋如果一本书本身就是正方形比如 (7, 7)旋转之后还是 (7, 7)并不会产生第二种候选方案。归一化处理天然把这种情况收敛成一个候选不需要额外去重正好符合题意。2.2 排序方向长度升序、宽度降序背后的原因这是整道题最容易翻车的细节。我们的目标是把二维问题降成一维DP所以必须先排序。常见标准写法是按长度升序如果长度相同按宽度降序。你可能会问为什么宽度要降序升序不行吗可以这么理解。我们最终要在一个序列里找出若干本书叠成一摞下标越靠后的书长度越有资格成为更底层的那本。在 DP 过程中我们只往前找“能放在它上面的书”。如果长度相同这两本书不可能叠在一起因为叠放要求严格小于长度相等连比较都不用比。但它们出现在排序结果里的时候如果宽度也升序就会出现“前面的宽度小、后面的宽度大”的假象某些二分优化的写法会误以为它们能构成递增关系。为了避免这种歧义长度相同时让宽度降序这样同一长度的书在宽度方向上天然是下降的不可能被误选成一条合法的递增链。你可能会说我的 DP 转移里明明写了 up.len down.len 这个条件长度相同会被拦下来为什么还要费劲控制宽度顺序这话没错在纯 O(n^2) DP 里就算宽度升序靠条件判断也能兜住。但一旦你想换成树状数组、二分LIS等优化写法排序方向错误就会直接导致答案偏大。所以从标准姿势开始就按“长度升序长度相同宽度降序”来后面再怎么优化都不会出问题。2.3 状态定义与转移方程排序完成之后就是动态规划部分。这里要特别注意题目如果是求最大高度状态就不能只存“数量”。定义 dp[i] 表示以第 i 本书作为最下面那一本时这摞书能达到的最大总高度。初始化时每本书至少能单独成摞所以 dp[i] 第 i 本书的高度。然后遍历排在它前面的所有书 j如果第 j 本书的长和宽都严格小于第 i 本书那么第 j 本书可以放在第 i 本书上面于是候选结果是 dp[j] 第 i 本书的高度。取最大值更新 dp[i]。最后答案不是 dp[最后下标]因为最优解不一定以排序后最后那本书作为底层所以要对所有 dp[i] 取最大值。转移方程可以写成dp[i] h[i] max( dp[j] )其中 j i 且 len[j] len[i] 且 wid[j] wid[i]如果不存在这样的 jdp[i] h[i]。这里我为什么要强调 dp[j] 是“以 j 为底层的最大高度”而不是“ j 这个点的某种长度”因为 dp[j] 已经包含了 j 下方那一整条合法链的总高度。根据“严格小于”关系的传递性只要 j 能放在 i 上面那么 j 下面的所有书也一定都能放在 i 上面因为那些书长宽都小于 j而 j 又小于 i。这保证了直接把 dp[j] 拿过来用不会破坏约束条件。如果题目求的是“最多能叠几本书”而不是最大高度处理更简单把所有书的高度都当成 1或者初始化 dp[i] 1转移时用 dp[j] 1。一套模板通吃两种问法。3. Java代码完整落地3.1 数据结构与输入解析先解决输入问题。我建议定义一个 Book 静态内部类字段就是书名、长、宽、高。在解析的时候直接完成归一化len Math.max(a,b)wid Math.min(a,b)这样后面比较统一。输入格式不固定我写了一段兼容代码能解析“书名 长 宽 高”四段也能解析“长 宽 高”三段。如果只有三个数字就用“B0”“B1”这种自动生成书名方便最后输出路径。这里有个经验机考环境里输入样例经常带有多余空格甚至空行。用sc.nextLine()读一行后trim()再按空白字符分割比用nextInt()一个个读更稳。尤其有些变体第一行就是书数量但也有的版本直接连续输入直到 EOF兼容性代码能省很多麻烦。3.2 核心代码实现下面是完整可运行的 Java 实现。这段代码以“求最大叠放总高度”为主最后输出叠放顺序。import java.util.*; public class BookStack { static class Book { String name; int len; int wid; int height; Book(String name, int len, int wid, int height) { this.name name; this.len len; this.wid wid; this.height height; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); // 第一行书本数量 int n Integer.parseInt(sc.nextLine().trim()); ListBook books new ArrayList(); for (int i 0; i n; i) { String[] parts sc.nextLine().trim().split(\\s); // 支持两种输入书名 长 宽 高或者 长 宽 高 if (parts.length 4) { String name parts[0]; int a Integer.parseInt(parts[1]); int b Integer.parseInt(parts[2]); int h Integer.parseInt(parts[3]); books.add(new Book(name, Math.max(a, b), Math.min(a, b), h)); } else { int a Integer.parseInt(parts[0]); int b Integer.parseInt(parts[1]); int h Integer.parseInt(parts[2]); books.add(new Book(B i, Math.max(a, b), Math.min(a, b), h)); } } // 关键排序长度升序长度相同宽度降序 books.sort((o1, o2) - { if (o1.len ! o2.len) { return o1.len - o2.len; } return o2.wid - o1.wid; }); int m books.size(); int[] dp new int[m]; int[] pre new int[m]; Arrays.fill(pre, -1); int best 0; int bestIdx -1; for (int i 0; i m; i) { Book down books.get(i); dp[i] down.height; for (int j 0; j i; j) { Book up books.get(j); // 严格小于长、宽都要更小 if (up.len down.len up.wid down.wid) { int candidate dp[j] down.height; if (candidate dp[i]) { dp[i] candidate; pre[i] j; } } } if (dp[i] best) { best dp[i]; bestIdx i; } } System.out.println(best); // 输出叠放书单从最上面一本到最下面一本 ListString path new ArrayList(); for (int cur bestIdx; cur ! -1; cur pre[cur]) { path.add(books.get(cur).name); } Collections.reverse(path); if (!path.isEmpty()) { System.out.println(String.join( - , path)); } } }这个代码有几个关键点值得反复看一是排序比较器。长度不同比长度长度相同比宽度且是倒序。二是dp[i] down.height这个初始值它代表“这一摞只有这本书自己”。漏掉这一行所有答案都会比正确答案少一个高度是最常见的低级错误。三是转移条件里用的是而不是因为题目说的是严格小于。四是pre[i] j记录路径如果题目只问高度这段记录可以直接不要但保留下来对调试验证很有用。3.3 路径回溯如何把叠放书单打出来路径回溯的思路很简单每次更新 dp[i] 的时候用 pre[i] 记下最优的前驱节点 j。等整个 DP 跑完从 bestIdx 开始沿着 pre 数组一直往前跳就能得到从最顶层到最底层的完整链路。因为 pre 是从后往前记录的所以最后要 reverse 一下再从最顶层开始输出。比如输出结果可能是B1 - B4 - B7意思是最上面是 B1最下面是 B7。这里有一个调试技巧你可以在本地随便造几组数据把路径打出来看看是不是合法的。比如最下面那本书的长宽一定最大越往上长宽越小。如果输出路径里出现“前面的书长宽反而比后面大”那说明排序方向写反了或者转移条件写错了。路径回溯不只是为了满足输出要求它更是定位问题的好工具。4. 常见问题与易错点排查4.1 长宽严格小于与旋转条件最容易踩的坑是“严格小于”理解不到位。有些题目描述会说“上面的书要比下面的书小”很多人在写代码时就会顺手写成这是错的。场景想一下上下两本书长宽都相等它们平稳叠放没问题但题意要求的是严格小于所以这种相等的情况不能算合法叠放。还有一个坑是旋转处理。有同学在归一化之前就直接开始排序和DP这样会漏掉很多正确答案。举个例子一本书原始数据是 (8, 10)另一本是 (12, 9)。如果不旋转直接比较8 12 满足但 10 9 不满足代码会判断放不下。可是把第一本旋转成 (10, 8) 后10 12 且 8 9就能放下了。归一化的作用就在这里。如果你发现自己样例输出比预期小优先检查是不是忘了处理旋转。4.2 排序错误导致的错误结果如果排序写成了“长度升序、宽度也升序”在纯 O(n^2) DP 里因为有严格条件兜底不一定爆错但一旦你后续想做二分优化结果就可能偏大。我建议如果你想验证自己排序方向对不对可以构造一组特殊数据两本书长度相同比如 (12, 10, 3) 和 (12, 8, 4)另一本 (13, 9, 5)。正确情况下长度相等的那两本不能叠最合理的链可能是 (12, 8, 4) - (13, 9, 5)总高度 9如果是错误排序或错误转移可能会把 (12, 10, 3) 算进链里得到更大的错误答案。这种反例其实给了我们一个很实用的自测方法测试数据里专门包含长宽相等的对子、长度相等宽度不同的对子、旋转后才成立的组合。三组数据跑通这道题的代码基本就稳了。4.3 初始值、溢出和输入格式初始值漏加自身的坑前面提到过这里再说一个相关的变体如果题目给的高度可能很大dp 数组建议直接用 long避免在求总高度的时候整数溢出。尤其是后续优化版本里累加很多本书的高度int 不一定够。输入格式也是一个不稳定因素。有些版本书名里可能没有空格但也有可能出现“书名 长,宽,高”这种逗号分隔的输入。我上面给出的代码只兼容了空格和 Tab如果你遇到逗号可以把split(\\s)改成更通用的分割方式或者先处理一下字符串。考试时第一件事就是看样例格式不要默认输入格式一定是你熟悉的。建议在代码开头自己写一个小循环把输入逐行打印出来确认一遍别嫌麻烦见过太多因为读错输入导致AC不了的例子。4.4 面试官问“能不能优化到 O(n log n)”这道题在机考里 n 一般不会特别大通常几百到一千出头O(n^2) 的 DP 完全够用你直接交没毛病。但如果你在跟面试官复盘可能会被追问能不能优化。先说结论可以把“宽度”离散化后用树状数组或线段树维护区间最大 dp 值把每次找最优前驱的过程从 O(n) 降到 O(log n)整体复杂度变成 O(n log n)。这里只讲思路代码如下。因为有了排序保证我们按顺序遍历时所有已经处理的、长度严格更小的书都已经在数据结构里了。转移时查询“宽度小于当前书宽度”的最大 dp 值当前书算完后再把 dp[i] 按它的宽度位置插入树状数组。不过要注意这只在求“数量”的时候可以直接套经典二分LIS求“带高度权重”的最大和时二分LIS不能直接用必须用带权数据结构。这也是很多同学知道“可以二分优化”但实现起来一头雾水的原因。我建议机考阶段先把 O(n^2) 的朴素 DP 写熟优化属于加分项不是必选项。5. 考场实战与刷题建议5.1 双机位机考环境下怎么保证ACOD机考是双机位监考也就是主摄像头拍屏幕和上半身副摄像头从侧后方拍环境。这种模式下你不可能像平时刷题那样随时翻笔记所以考前把模板代码练到肌肉记忆很重要。我的经验是常用 DP 模板提前在本地 IDE 里跑通考场上只改输入解析和数据模型核心逻辑不要临时想。另外注意机考的输入输出要求一般就是从 System.in 读、往 System.out 写不需要打印额外提示信息。有些人喜欢在输出前加一句System.out.println(答案是)这种多余输出在本地跑没问题在判题系统里直接给你判WA千万注意。时间分配上C卷整体题量不小如果前面有简单题先保证简单题AC再回头啃这道题。书籍叠放写起来很快但调试可能需要一点时间。我就是先花十秒钟看穿它是二维LIS然后直接套模板一次跑通比临时推状态转移稳太多了。5.2 一类二维偏序题目的举一反三这道题会了之后建议立刻把下面几道题也过一遍信封嵌套、堆箱子、俄罗斯套娃信封、叠罗汉。它们的核心都是“先排序降一维再做带权LIS”。信封嵌套通常只求最多套几层对应的是把高度全部看成1的版本堆箱子可能涉及多维度选择但排序和DP骨架完全一致。我有一个个人习惯把这类题的模板抽象成一个通用函数输入是二维坐标加权重输出是最大权重合法链。到了考场上不管题目包装成“书”“信封”还是“箱子”我都直接套这个函数。模板背熟之后最大的好处是省下大量思考时间把精力留给边界条件和调试。最后再分享一个小经验这种二维偏序DP代码真正核心的其实只有十行左右。如果你能不看答案独立把排序方向、DP初始值、转移条件、路径回溯写对那么这题就彻底是你的了。我建议你合上文章自己在编辑器里敲一遍再故意造几个带旋转和同长度的测试数据跑一跑。踩过一次坑之后这类题基本就再也不会错了。