企业官网建设流程全解析

上周有位准备校招的同学找我复盘某头部潮流电商平台的2026春招算法岗笔试题，3月21日那场的第三题叫“爬山”。题目本身不是生僻模型，但它正好卡在“暴力能想到、但暴力大概率超时”的经典位置上，用来筛选候选人有没有真正理解动态规划里的子问题拆分，非常典型。我把它完整拆了一遍，从题目描述到三种语言实现再到自测边界用例都整理在下面，打算参加今年春招的同学可以直接拿来当练习。

需要提前说明：涉及具体公司信息我统一用“某电商平台”代称。下面是原题回顾和完整解析。

1. 题目速览：原题描述、输入输出与考察点

1.1 原题描述与输入输出格式

题目给一个 n 行 m 列的整数矩阵，矩阵里每个数字代表该格子的山地高度。你可以从任意一个格子出发，每一步移动到上下左右相邻的四个格子之一，但目标格子的高度必须严格大于当前格子的高度。同一个格子只能经过一次。问：在遵守规则的前提下，最多能访问多少个格子。

换句话说，就是求矩阵中最长的“严格递增”相邻路径长度。

输入格式：

第一行两个整数 n, m 接下来 n 行，每行 m 个整数，表示每个格子的高度

输出格式：

一个整数，表示最长严格递增路径的长度

示例输入：

3 3 9 9 4 6 6 8 2 1 1

示例输出：

4

示例里的一条合法最长路径是 1 -> 2 -> 6 -> 9，长度 4。注意有两处高度 9 和两处高度 6，因为要求严格递增，所以相等的格子之间不能互相转移。

1.2 为什么“严格递增”这个条件决定了一切

如果题目允许相等高度之间移动，那路径就可能出现环，问题就从最长路径变成带环图上的最长路径，难度直线上升，通常需要状态压缩之类的手段。

加了“严格递增”之后，整张图变成一个有向无环图（DAG）：从低处指向高处，方向永远不可能绕回低处，所以不存在环。在 DAG 上求最长路径有非常成熟的做法，既可以记忆化搜索，也可以按拓扑序做动态规划。这道题的核心考点就在这里。

1.3 数据范围决定了算法上界

笔试给出的范围一般是 1 <= n, m <= 200，也就是最多 40000 个格子。高度值可能到 10^9 级别，但这个不影响做法，只影响你用 int 还是 long long，Java 里用 int 足够了。

40000 个点的规模提示我们：

• O(n^2 * m^2) 这种暴力枚举复杂度在极限数据下会到 1.6 * 10^9，必挂
• O(n * m) 或者 O(n * m * log(n * m)) 的算法比较稳妥

也就是说明确要求你放弃“每个起点重新搜一遍”的朴素思路，去用动态规划的记忆化手段。

2. 先想清楚暴力为什么不可行，再谈正解

2.1 每个点都深搜：复杂度是怎么爆掉的

最容易想到的解法是：枚举每个格子作为起点，从起点出发递归四个方向，看能走多远。我模拟一下这个过程：

for 每个格子 (i, j): ans = max(ans, dfs(i, j))

dfs 里逐层向更高处走。在随机数据下，路径一般不会太长，这么写可能还能蒙混过关；但在故意构造的递增矩阵里，路径可以从最小值一路连到最大值，几乎覆盖全图。比如一个 200x200 的蛇形递增矩阵，最长路径长度能达到 39999。如果从每个格子都重新走一遍，每一步又都向四个方向扩散，总计算量会接近 O((n*m)^2)，也就是 16 亿次级别。笔试直接超时。

2.2 重复计算藏在路径交叉的地方

假设矩阵里有两条不同的路径都经过同一个高点 X：

• 从 A 出发走到 X，后续还能走 10 步
• 从 B 出发走到 X，后续同样还能走 10 步

如果不做缓存，这两次搜索会在 X 处把“从 X 出发还能走多远”重复计算一遍。路径交叉越多，重复越严重。

这其实就是动态规划里最常见的“重复子问题”。一旦你意识到“从某个格子出发的最长路径”是固定的、可复用的值，解法就呼之欲出：用一个表把结果存起来，下次再遇到直接取。

2.3 从终点倒推：最优子结构

定义 dp[i][j] 表示从格子 (i, j) 出发能走的最长路径长度。

假设 (i, j) 的四个相邻方向里，某个方向 (ni, nj) 的高度大于 height[i][j]，那从 (i, j) 出发可以走一步到达 (ni, nj)，再继续沿 (ni, nj) 出发的最优路径走，所以：

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

如果四个方向都没有更高点，那么 dp[i][j] = 1，表示只能停在这个格子。

这个递推式依赖的是“更高的相邻格子的 dp 值”。由于高度严格上升，从任意格子出发往高处追，最终都会终止在一个“局部最高点”，所以递归天然有边界，不需要手动处理环。

2.4 两条实现路线：记忆化搜索 vs 排序动态规划

实现上有两条路：

• 记忆化搜索：用 DFS 递归计算 dp[i][j]，每次先查表，没算过就算，算完存表。
• 排序动态规划：把 40000 个格子按高度从小到大排序，然后按顺序处理。处理某个格子时，它所有更低的邻居都已经算过，可以直接用来更新它。

两种方法本质一样，都是 O(n*m)。区别在于写法。DFS 代码短、思路直观，但在极端情况下递归深度可能达到 40000，造成栈溢出；排序 DP 是迭代写法，没有递归深度问题，更稳。我下面会给出两个版本的代码。

3. 两套正解：记忆化 DFS 与排序 DP 的完整推导

3.1 方案 A：记忆化 DFS，代码最短

记忆化 DFS 的伪代码如下：

dfs(x, y): 如果 dp[x][y] 已经算过，直接返回 dp[x][y] best = 1 依次看四个邻居： 如果邻居高度 > height[x][y]: best = max(best, 1 + dfs(邻居)) 保存 dp[x][y] = best 返回 best

主函数里遍历每个格子，调用 dfs，取最大值。

这套代码最容易写错的地方是忘记判断边界，或者忘掉“严格大于”而写成“大于等于”。另外注意初始值用 0 表示“未计算”，因为任何格子的 dp 值至少是 1。

3.2 方案 B：按高度排序的迭代 DP，笔试更稳

这里我重点展开迭代方案，因为它在笔试中最不容易出问题。

先准备一个列表，把每个格子存成三元组 (height, x, y)。按 height 从小到大排序。再开一个二维数组 longest，longest[x][y] 表示以 (x, y) 结尾的最长严格递增路径长度，初始化全部为 1。

按高度从小到大遍历每个格子时，去看它的四个邻居。如果邻居的高度小于当前格子高度，说明这个邻居是“从低处走向当前格子”的前驱，而且因为我们是按高度升序处理的，这个邻居的 longest 值一定已经算好了。此时可以更新：

longest[cur] = max(longest[cur], longest[neighbor] + 1)

遍历完所有格子后，答案就是整个 longest 数组里的最大值。

这里有个细节：高度相等的格子不能互相转移，所以排序时相同高度的格子之间的先后顺序不影响结果。我们只在邻居高度严格小于当前格子的情况下做更新，天然规避了相等高度的问题。

3.3 复杂度分析：两种方法都够用

记忆化 DFS 每个格子只会被真正计算一次，每次计算固定看四个方向，时间复杂度 O(nm)，空间复杂度 O(nm)，递归栈空间另算。

排序 DP 需要对 40000 个格子排序，时间复杂度 O(nmlog(nm))，空间复杂度 O(nm)。40000 个点排序非常快，在实际笔试里通常和 O(n*m) 的差距可以忽略。

如果追求理论最优，也可以用拓扑排序 + DP 做到严格 O(n*m)，但需要额外建图或者处理入度，代码复杂度上去了。对笔试场景来说，排序 DP 已经足够稳。

4. Java、C++、Python 三语言实现与避坑注释

4.1 Java：迭代排序写法

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] height = new int[n][m]; List<int[]> cells = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { height[i][j] = sc.nextInt(); cells.add(new int[]{height[i][j], i, j}); } } // 按高度从小到大排序 cells.sort((a, b) -> a[0] - b[0]); int[][] longest = new int[n][m]; for (int i = 0; i < n; i++) { Arrays.fill(longest[i], 1); } int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; int ans = 1; for (int[] cell : cells) { int x = cell[1]; int y = cell[2]; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && height[nx][ny] < height[x][y]) { longest[x][y] = Math.max(longest[x][y], longest[nx][ny] + 1); } } ans = Math.max(ans, longest[x][y]); } System.out.println(ans); } }

注意cells.sort((a, b) -> a[0] - b[0])这里三元组里第一个元素是高度，排序不会改变 x、y 的绑定关系，没问题。如果高度差值可能超过 int 范围，可以改成Integer.compare(a[0], b[0])更安全。

4.2 C++：优先掌握迭代写法

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> height(n, vector<int>(m)); vector<array<int, 3>> cells; // {height, x, y} for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> height[i][j]; cells.push_back({height[i][j], i, j}); } } sort(cells.begin(), cells.end()); vector<vector<int>> longest(n, vector<int>(m, 1)); int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int ans = 1; for (auto &cell : cells) { int x = cell[1]; int y = cell[2]; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && height[nx][ny] < height[x][y]) { longest[x][y] = max(longest[x][y], longest[nx][ny] + 1); } } ans = max(ans, longest[x][y]); } cout << ans << endl; return 0; }

C++ 里 vector 默认初始化为 0，longest我显式用vector<int>(m, 1)初始化成 1，省得后面手动 fill。

4.3 Python：递归版要小心，迭代版最稳妥

先给迭代版：

import sys def main(): data = list(map(int, sys.stdin.read().split())) if not data: return n, m = data[0], data[1] idx = 2 height = [] cells = [] for i in range(n): row = [] for j in range(m): h = data[idx] idx += 1 row.append(h) cells.append((h, i, j)) height.append(row) cells.sort(key=lambda x: x[0]) longest = [[1] * m for _ in range(n)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] ans = 1 for h, x, y in cells: for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < n and 0 <= ny < m and height[nx][ny] < h: longest[x][y] = max(longest[x][y], longest[nx][ny] + 1) ans = max(ans, longest[x][y]) print(ans) if __name__ == "__main__": main()

Python 的递归版我也贴一下，因为很多人面试时想讲记忆化搜索：

import sys sys.setrecursionlimit(1000000) def solve(): data = list(map(int, sys.stdin.read().split())) if not data: return n, m = data[0], data[1] idx = 2 height = [] for i in range(n): height.append(data[idx:idx + m]) idx += m dp = [[0] * m for _ in range(n)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def dfs(x, y): if dp[x][y] != 0: return dp[x][y] best = 1 for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < n and 0 <= ny < m and height[nx][ny] > height[x][y]: best = max(best, 1 + dfs(nx, ny)) dp[x][y] = best return best ans = 1 for i in range(n): for j in range(m): ans = max(ans, dfs(i, j)) print(ans) if __name__ == "__main__": solve()

这里必须强调：递归版虽然思路清晰，但在极端递增数据下可能触发 Python 的递归深度上限。就算用sys.setrecursionlimit(1000000)，实际运行时也可能因为 C 栈不够而报段错误。所以我个人建议，笔试环境优先用迭代排序 DP，面试讲解时再提记忆化思路。

5. 在线自测指南：用样例和边界用例验证代码

标题里提到在线测试，实际笔试环境一般不会给你太多调试机会，自己平时练习时就得把测试用例准备好。我把自己常用的一组用例放在下面，建议拿到代码后逐个跑一遍。

5.1 先用手算样例验证

3 3 9 9 4 6 6 8 2 1 1

期望输出 4。这个例子用来确认“严格大于”是否正确，以及相同高度值之间不会形成路径。

5.2 螺旋递增矩阵：最考验实现方式的用例

3 3 1 2 3 8 9 4 7 6 5

期望输出 9。整个矩阵从 1 到 9 可以绕一圈走完，路径长度是 9。这个用例对递归版很不友好，因为递归深度正好是 9，小矩阵没事，但如果改成 200x200 的螺旋递增矩阵，递归深度能到 39999，也就是我前面说的栈溢出场景。

5.3 全相等矩阵和单行矩阵

2 2 5 5 5 5

期望输出 1，因为所有格子高度相同，没有可以转移的方向，只能停在起点。

1 4 4 3 2 1

期望输出 4。虽然输入看起来是降序，但你可以从最小的 1 出发，走 1 -> 2 -> 3 -> 4，一共 4 个格子。这道题不要求路径方向，只要数字严格递增即可。

5.4 自动化对拍：用暴力DFS验证两个正解

我在本地练习时习惯写一个随机数据生成器，再写一个朴素暴力DFS，和迭代DP对拍。这里给一个 Python 对拍片段：

import random def brute(height, n, m): dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def dfs(x, y): best = 1 for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < n and 0 <= ny < m and height[nx][ny] > height[x][y]: best = max(best, 1 + dfs(nx, ny)) return best ans = 1 for i in range(n): for j in range(m): ans = max(ans, dfs(i, j)) return ans def sort_dp(height, n, m): cells = [(height[i][j], i, j) for i in range(n) for j in range(m)] cells.sort(key=lambda x: x[0]) longest = [[1] * m for _ in range(n)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] ans = 1 for h, x, y in cells: for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < n and 0 <= ny < m and height[nx][ny] < h: longest[x][y] = max(longest[x][y], longest[nx][ny] + 1) ans = max(ans, longest[x][y]) return ans for _ in range(1000): n = random.randint(1, 5) m = random.randint(1, 5) height = [[random.randint(0, 9) for _ in range(m)] for _ in range(n)] a = brute(height, n, m) b = sort_dp(height, n, m) if a != b: print("mismatch", height, a, b) break else: print("all ok")

随机对拍能查出排序方向写反、边界判断漏掉等隐蔽问题。我建议你写完代码后不要只跑示例，至少再跑一个全相等矩阵和一个单列矩阵。

5.5 这几个各语言易错点务必留意

我把练习时踩过的坑汇总成表格：

6. 复盘：第三题的位置决定了它的考察重点

6.1 这道题在筛什么能力

笔试第三题通常不像第四题那样需要复杂的数学建模，但一定比前两道“一眼题”更有区分度。“爬山”这道题真正考察三件事：

• 能不能从“搜索”快速过渡到“记忆化”
• 能不能识别出“严格递增”带来的 DAG 性质
• 会不会处理大数据范围下的递归深度风险

很多人卡在第二点，拿到题就写 DFS，写完才发现复杂度不对。其实只要在草稿纸上画一个简单矩阵，标出从低到高的方向，就会意识到这是一个有方向、无环的图。

6.2 笔试现场怎么分配时间

我的建议是：

• 读题加画样例：3 到 5 分钟
• 确定模型：看到最长路径、无环、40000 点，立刻想到 DP 或记忆化，5 分钟内
• 写代码：迭代排序 DP 大约 15 分钟，记忆化 DFS 大约 10 分钟
• 自测：至少跑示例和全相等矩阵，5 分钟

这样总耗时控制在 30 分钟左右，留出时间给第四题。如果 15 分钟内没思路，先用暴力 DFS 拿部分分，再尝试加一个 memo 数组。

6.3 如果当场想不起来动态规划怎么写

最保险的兜底方案是写一个不带记忆化的 DFS，先把小数据分拿满。然后观察自己的 DFS 里哪里重复计算了，加一个二维数组缓存返回值即可。大多数情况下，“暴力 DFS + 缓存表”就是记忆化搜索，不需要额外想状态转移。

7. 最后想多说两句

这道题做完之后我最大的感受是：它其实是在提醒我们，遇到“路径”“最长”这类词，先画图、再定模型，而不是急着写循环。我自己第一次做类似的矩阵最长递增路径题时，也犯过“每个起点都 DFS”的错误，后来被极限数据教训过一次才长记性。

如果备考时间充裕，建议把这道题和经典的矩阵最长递增路径放一起对比练习，把迭代排序 DP 和记忆化 DFS 都写一遍。尤其要亲手构造一个 200x200 的螺旋递增矩阵，跑一跑自己的代码，看会不会超时、会不会爆栈。经历过一次，笔试现场就不会慌了。