企业官网建设流程全解析

蚂蚁春招线上笔试，3月15日开发岗第一题叫“搭房子”。考完看到交流群里很多人在对这道题：有人直接两层循环枚举，样例都没跑完就超时；有人以为是贪心，排序后从左往右塞，结果在“严格大于”这个条件上反复WA；还有人在“积木可以旋转90度”这个条件上卡了很久，不知道该怎么统一比较方式。我当时整理出的一套稳定解法，核心其实就一句话：把二维的大小关系排序成一维，然后跑最长上升子序列（LIS）。

这篇文章把完整题面、推导过程和Java、C++、Python三版实现都记录下来，也附上我在在线测试环境里会用到的自检方法。题目本身不算难，但非常典型——剥掉“搭房子”的外壳，本质就是二维偏序最长链，这类考点在笔试里出现频率很高，值得彻底吃透。

1. 题目拆解：这题到底在考什么

1.1 还原题面：积木的“长与宽”怎么描述

先说清楚，这里给出的题面是根据多人回忆和常见题库整理出来的通用版本。真实笔试时可能存在个别措辞差异，但核心数据结构、数据范围和判定规则基本一致：

有n块积木，第i块积木长l_i、宽w_i。把一块积木放在另一块积木上面时，要求上面积木的长和宽都严格小于下面积木的长和宽。每块积木可以旋转90度再使用（也就是长宽可以互换），每块积木最多用一次。现在问：最多能搭多少层？

数据范围方面，n一般给到10^5级别，l_i和w_i给到10^9级别。这个范围非常关键，它直接决定暴力做法不可行，也决定我们最终必须用O(n log n)级别的算法。

1.2 无脑的双层循环会超时：先估一下复杂度

如果没做过类似的题，第一反应肯定是枚举两块积木，判断能不能上下叠放，然后做动态规划。设dp[i]表示以第i块积木为最底层时最多能搭多少层，转移时就遍历所有能与它形成“下面关系”的积木j：

dp[i] = max(dp[i], dp[j] + 1)

这个思路本身没错，但复杂度是O(n²)。当n=10^5时，循环次数是10^10级别，别说在线测试了，就算在自己电脑上跑样例都要好几秒甚至更久，放在笔试环境里基本等于直接超时。

所以问题的关键不是会不会写DP，而是怎么把复杂度降下来。能降到O(n log n)的思路，就是排序+LIS。

1.3 旋转的条件，反而帮我们统一了比较方式

先说旋转这个点怎么处理。每块积木可以旋转，意味着一块长10宽2的积木，和一块长5宽3的积木，能不能叠起来，要看旋转后是否存在一个朝向能让长宽都严格小于另一块。

有一个很常见的套路：对每块积木取(max(l, w), min(l, w))。这样处理后，积木的有效朝向就被“规范化”了：无论原来怎么旋转，比较时都按“长边对长边、短边对短边”来比。为什么这样做是对的？因为如果积木A能叠在积木B上，那么一定能找到一种摆放方式，让A的长边小于B的长边，同时A的短边也小于B的短边；反过来也成立。所以旋转这个条件不但没有增加复杂度，反而让我们少考虑四种朝向组合，直接统一成“两维都必须严格小”这一种比较规则。

很多人在这一步翻车，是试图把四种旋转情况都写进状态转移里，结果代码又长又容易错。其实用标准化后的二元组，问题就回归成最标准的二维偏序比较。

2. 核心思路：排序后套LIS的原理

2.1 从“二维比较”到“一维子序列”

现在我们有一堆二元组(a, b)，其中a = max(l, w)，b = min(l, w)。题目要求找一条尽可能长的链，使得链上后面一个二元组的a、b都严格大于前面一个二元组的a、b。这就是典型的二维偏序最长链。

二维偏序的处理套路很固定：先把第一维排好序，然后问题就只剩下第二维。把n个二元组按a从小到大排序，接下来我们只看b这个维度，找b的最长严格上升子序列。如果排序后的b序列满足严格递增，那就等价于原题中“a递增且b递增”的合法叠放链。

需要注意的是一点：排序后b的递增长度，必须对应原题中严格大于的关系；如果只是b不下降，但a相等，那就不合法。这引出下一个排序细节。

2.2 排序细节：同一宽度下，为什么高度要降序

排序不是简单按a升序排。正确做法是：按a升序；当a相等时，按b降序。为什么？

看反例。假设有两块积木标准化后都是a = 2，一块b = 10，另一块b = 11。如果按b升序排，b序列就是10, 11，LIS长度会算成2，让人误以为可以叠成两层。但实际上两块积木的a都是2，宽度相同，根本不能互相叠放，正确答案应该是1。

把b改成降序后，同样一组数据变成11, 10，严格LIS长度是1，这样就正确阻断了同一宽度内部的非法链接。再看一个更充分的情况：有两块宽度2的积木，后面再跟一块宽度3的积木。排序后b序列可能是11, 10, 12，LIS可以选10, 12，长度2。这时答案正确吗？正确。宽度2的两块中任选一块，叠在宽度3的积木下面，正好2层，完全合法。这里的降序排序没有误伤合法答案，只是堵住了“a相等却互相叠”的漏洞。

2.3 二分LIS：d数组的维护逻辑和边界含义

常规动态规划求LIS是O(n²)，这里还要再优化一层，用贪心+二分把LIS降到O(n log n)。具体方法是维护一个d数组，d[i]表示长度为i+1的严格上升子序列中，末尾元素能达到的最小值。

遍历排好序的每个二元组时，拿到它的b值，在d数组里用lower_bound找到第一个不小于b的位置：

• 如果这个位置是d.end()，说明当前b可以接在现有最长序列后面，那么把它追加到d末尾，最长长度加1；
• 如果这个位置存在，说明存在某个长度的子序列，它的结尾可以变得更小，于是用b替换掉这个位置的d值。

这样d数组始终单调递增，而d的长度就是答案。整个过程里，每个元素只处理一次，每次都是O(log n)的二分，总复杂度O(n log n)，完全压得住10^5的数据量。

这里最容易混淆的点是：为什么用lower_bound而不是upper_bound？因为题目要求严格大于，所以遇到相等的b时不能接在后面；lower_bound会返回第一个不小于b的位置，刚好把相等的值覆盖掉，避免错误增长。“不小于”这个二分语义和“严格递增”的判定天然匹配。

3. Java / C++ / Python 三版实现与踩坑

3.1 Java实现：排序Lambda + 手写二分

Java里最方便的方式是把每块积木标准化后放进二维数组，然后直接用Arrays.sort配合Lambda排序。因为Java工具类没有现成的lowerBound，需要手写一个二分函数。

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] blocks = new int[n][2]; for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int l = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); blocks[i][0] = Math.max(l, w); blocks[i][1] = Math.min(l, w); } Arrays.sort(blocks, (x, y) -> { if (x[0] != y[0]) return Integer.compare(x[0], y[0]); return Integer.compare(y[1], x[1]); }); int[] d = new int[n]; int len = 0; for (int[] b : blocks) { int idx = lowerBound(d, len, b[1]); d[idx] = b[1]; if (idx == len) len++; } System.out.println(len); } static int lowerBound(int[] arr, int len, int key) { int l = 0, r = len; while (l < r) { int mid = (l + r) >>> 1; if (arr[mid] < key) l = mid + 1; else r = mid; } return l; } }

Java这里最容易出问题的地方是输入。很多在线笔试的输入量比较大，用Scanner读10^5行虽然也能过，但速度明显慢。换成BufferedReader加StringTokenizer会更稳。另一个坑是Lambda排序在Java 8以后才支持，部分老版本在线环境可能不支持，如果遇到编译错误，可以改成匿名内部类写法。

3.2 C++实现：pair排序 + lower_bound

C++写这道题非常顺，因为标准库直接提供了sort和lower_bound，pair也能直接比较。注意lower_bound默认找的是“第一个不小于给定值的元素”，正好对应严格LIS的需求。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int, int>> v; v.reserve(n); for (int i = 0; i < n; i++) { long long l, w; cin >> l >> w; long long mx = max(l, w); long long mn = min(l, w); v.push_back({(int)mx, (int)mn}); } sort(v.begin(), v.end(), [](const auto& x, const auto& y) { if (x.first != y.first) return x.first < y.first; return x.second > y.second; }); vector<int> d; for (auto& p : v) { auto it = lower_bound(d.begin(), d.end(), p.second); if (it == d.end()) d.push_back(p.second); else *it = p.second; } cout << d.size() << '\n'; return 0; }

C++版本里一开始读l和w我用的是long long，后面存pair时转成int。这道题数据范围给到10^9，int完全够用，转int不损失精度；如果数据范围没说死或更大，那么pair里也应该存long long，d数组也要用long long。比较安全的习惯是：不确认范围时一律用long long，避免因为一句“我觉得能装下”造成溢出。

3.3 Python实现：key函数 + bisect_left

Python里排序用key函数非常灵活，同一宽度降序直接写成lambda x: (x[0], -x[1])。LIS二分用标准库bisect_left，它返回第一个不小于目标值的位置，语义上也正好。

import sys from bisect import bisect_left def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) blocks = [] p = 1 for _ in range(n): l = int(data[p]) w = int(data[p + 1]) p += 2 mx, mn = (l, w) if l > w else (w, l) blocks.append((mx, mn)) blocks.sort(key=lambda x: (x[0], -x[1])) d = [] for _, h in blocks: i = bisect_left(d, h) if i == len(d): d.append(h) else: d[i] = h print(len(d)) if __name__ == "__main__": main()

Python这里要重点提醒：sys.stdin.buffer.read()一次性读入要比逐行input()快非常多。10^5行数据逐行读虽然也不至于超时，但加上排序和二分后，读入可能成为最大的时间消耗点。用split()把全部字节切成token再转int是笔试环境里最稳妥的写法。

3.4 三语言对比和各自容易踩的坑

三份代码逻辑完全一致，只是语言语法不同。核心流程都是：标准化每块积木的长宽，按第一维升序、第二维降序排序，再对第二维求严格LIS。

3.5 构造样例验证答案正确性

光看代码跑通过还不够，最好自己构造几个有代表性的样例，尤其要覆盖“重复积木”和“同宽不同高”这两种边界。

样例一：

输入：

5 1 1 1 1 2 2 3 3 4 4

这个样例里有两块完全相同的1×1积木。正确答案是4，也就是取一块1×1、一块2×2、一块3×3、一块4×4，叠成4层。如果把排序后的b序列列出来，会看到1和1相邻，严格LIS不会把两个都选上，结果正好是4。这个用例专门用来验证算法不会把相同的积木重复算进链里。

样例二：

4 2 2 1 3 4 4 3 5

标准化后是(2,2)、(3,1)、(4,4)、(5,3)，排序后b序列是2,1,4,3，LIS长度是2。直观上看，确实只能组成两层，比如把旋转后的1×3积木放在3×5积木上面。这个用例用来验证中等复杂度的数据。

构造完样例后，我建议考前自己再写一个暴力版本对拍：随机生成n不超过100的小数据，暴力O(n²)求答案，和优化版答案比对几百组，确认没有不一致。这个习惯我在笔试前一直保留，它能快速发现那些“样例过了但思路有漏洞”的问题。

4. 考场延伸与在线测试自检

4.1 最容易WA的三个边界条件

第一是“严格大于”误写成“大于等于”。这是最隐蔽的坑，样例通常测不出来，但在大量随机数据对拍时一定会暴露。如果题目要求严格，就保持题目原样处理；如果题目改成了“不严格小于”，那二分也要从lower_bound换成upper_bound，排序策略还要重新推，不能直接改一个函数就完事。

第二是旋转后的比较基准。有些人在比较积木A和积木B时直接比原始l和w，忘了积木可以旋转之后存在两种朝向。这种错误在样例里偶尔能过，但构造一组“长宽相差很大”的数据就能立刻暴露。标准化成(max, min)是比较安全的做法。

第三是数据范围。虽然这题给到10^9，int能装下，但有些题目的变体会把数值放到2^31-1以上，或者在实际累加时超过int范围。笔试时最稳的做法是先看数据范围再决定类型，不确定时直接上long而不是赌它不超。

4.2 在线测试中的输入输出与性能

在线笔试环境一般会限制单题运行时间，常见是1秒到2秒。这份代码整体O(n log n)，n=10^5时非常快，主要性能差异就在IO。我在实际测试里对比过：Java的Scanner读10^5行和BufferedReader读同样数据，耗时有明显差距；Python逐行input()和一次性read()差距更大，最高可能差出一倍以上。所以三份代码里我都优先使用了更快的输入方式。

输出倒没什么坑，注意最后一定带换行。很多在线测评系统对“最后一行有没有换行”不敏感，但格式错误还是尽量避免。如果一道题有多个测试点，输出格式不统一或有多余空格，偶尔也会被判WA。

4.3 这类“搭房子”还有哪些变体

“二维偏序最长链”这个模型在笔试里换过很多马甲，至少见过以下几种：

第一种是“不旋转版本”。直接给积木长宽，不允许旋转，这时就不需要做(max, min)标准化，其余思路完全一样。

第二种是“允许相等”版本。如果题目改成“长和宽都不小于下面的积木”，那么偏序关系变成非严格序。此时排序细节要调整，LIS二分也要从lower_bound改成upper_bound。不要小看这一个函数的变化，它会直接影响相同宽度积木能不能被选进同一条链。

第三种是“箱子堆叠”问题。每个箱子有长、宽、高三个属性，求最高能堆多少。这种三维问题如果把一个维度当成价值，用DP加离散化也能解，但复杂度明显变高，笔试里出现一般会限制n比较小。

第四种是“承重约束”版本。每块积木有重量和承重，上面所有积木的总重量不能超过下面积木的承重。这类题目的解法不是纯LIS，而是先排序后用带权DP，常见于更难的笔试压轴题。它的核心思想仍然是“先处理一个维度，再处理另一个维度”，和今天的思路一脉相承。

4.4 考前可用的自检清单

我在实际准备这类题目时，会给自己列一个简单检查清单，每次写完代码都过一遍：

• 每块积木是否做了旋转标准化处理？
• 排序规则是否满足“第一维升序、第二维降序”？
• 严格递增要求下，是否用的lower_bound而不是upper_bound？
• 重复积木是否会被误选进同一层？
• 输入是否用了更快的读取方式，而不只是“能跑就行”？
• 数据范围是否确认过，类型是否安全？

这套清单看起来琐碎，但能有效防止提交时最常见的低级失误。尤其是“严格”和“非严格”这两个词，题目每次都会用，但很多人读题时一带而过，最后WA了才发现是方向性问题。

我个人在复盘这道“搭房子”时最大的体会是：很多看起来像模拟题的题目，包装拆掉以后都是经典算法模型。如果你能从“积木旋转、长宽比较”这种描述里，快速意识到它其实是排序+LIS，那么剩下的事情只是把模板写对而已。刷题时多练这种“拆包装”的思维，比单纯记模板有用得多。