企业官网建设流程全解析

搜狗2020校招后端笔试第二场，有一道题让我印象特别深。当时考场里不少人卡在这一题上，出来之后群里讨论了半天。今天想把这道题完整拆一拆，复盘一下我当时是怎么一步步从读题到AC的，包括推导过程、踩过的坑，还有考后总结出来的更优解法。如果你正在准备校招笔试，尤其是后端方向，这道题值得认真过一遍。

1. 题目回顾与原题复现

先交代一下背景。搜狗2020校招后端笔试（第二场）的题型比较常规，前面是选择题，后面是两道编程题。编程题允许使用本地IDE，牛客网在线评测，语言不限。我选的是C++，但下面的思路用Java、Python也完全一样。

1.1 题目原文描述

这道题大概是这样说的：

定义一种特殊的数列，这个数列的第一个数始终为0。从第二个数开始，每一个数要么等于前一个数本身，要么比前一个数大1。给定一个长度为N的数组，需要你判断这个数组是否可能是上述特殊数列的某个前缀。如果可能是，再输出所有满足条件的前缀序列中，最后一个数的最小值是多少。

我记得考场上题目的表述比这稍微绕一点，涉及“有几个可能的序列”“末尾最小值”之类的说法，但核心就是上面这个意思。

1.2 关键条件梳理

这里有几条关键信息，每一条都会直接影响后面的解题方向：

• 首元素固定为0。这个条件把序列的起点锁死了，任何不以0开头的输入都可以直接判否。
• 相邻元素的差值只能是0或1。换句话说，a[i] - a[i-1]要么是0，要么是1，不允许出现负数差，也不允许出现大于1的正数差。
• 题目要求判断“是否存在至少一个合法前缀”，以及“末尾元素的最小可能值”。
• N的范围我记得是10^5级别，这就意味着O(N^2)的暴力做法在极限数据下会超时，必须设计O(N)的算法。

我先把这类题的精髓说一下：它表面上是个模拟题，看起来就是逐位检查差分，但真正落笔的时候你会发现，“末尾最小值”这个追问把难度抬高了一档。你不仅要判断可行性，还要在一堆合法序列里找最优解。这其实是一个披着模拟外衣的动态规划问题。

2. 核心思路拆解：从暴力到动态规划

2.1 先想清楚暴力解法

拿到这道题，第一反应肯定是暴力枚举所有可能的序列。假设N是10，每个位置最多有两种选择（保持或+1），那就有2^N种组合，逐个检查明显不现实。

那么退一步，能不能用贪心或者回溯来剪枝呢？回溯当然可以，每到一个位置就往两个方向探索，但这在最坏情况下依然是指数级的。

我考场上第一版代码就是回溯，写完之后自己构造了一个全0的边界数据，发现跑得还算快。但转念一想，如果N是10万，全0序列虽然看起来只有一种合法形态，回溯却会在每一层都进入“保持”分支，实际上是线性递归，倒是不会爆。可如果再构造一些差值为1的数据，让每个位置都有两个分支，瞬间就完蛋了。

所以暴力回溯只能作为理解题目的辅助工具，不能作为最终解法。

2.2 关键转化：末尾值范围的推导

先想想，假设前i个元素已经满足条件了，那么第i个元素可能的值有哪些？

由于第一个元素是0，每一个新元素要么等于前一个、要么比前一个多1，所以整个序列是单调不减的，且每个位置的值不会超过i - 1（因为从0开始，每步最多加1，走i-1步最多加到i-1）。

核心观察1：对于任意位置i，它的值必须严格满足0 <= a[i] <= i（这里我用0-based下标，所以第i个位置最多是i）。

为什么？因为从第0个位置（值为0）到第i个位置一共走了i步，每步最多增加1，所以值域上限是i。下限当然是0，因为序列从不下降。

但光有这个还不够，题目还要求判断给出的数组本身是否合法。

核心观察2：如果给出的数组满足差分约束（相邻差为0或1），并且首元素为0，那么这个数组本身就是一个合法的特殊序列前缀。

这一条其实很好理解——题目根本没有规定“唯一性”，只要数组自身满足构成规则，那它本身就是合法序列。换句话说，可行性判断其实很简单：首元素为0，且所有相邻差都在{0, 1}这个集合里。

2.3 “末尾最小值”的递推公式

既然可行性判断已经解决，剩下最难啃的骨头就是“在所有合法序列中，末尾元素的最小值”。

注意，给出的数组只约束了部分位置的“下限”。举个例子，如果输入是[0, 1, 1, 2, 2]，这个数组本身合法，所以末尾值可以是2。但有没有可能另一个合法序列也是以0、1、1开头，但第3个位置取1、第4个位置也取1，最后末尾是1呢？显然不行，因为输入第4个位置写死了是2，你必须尊重输入数据。

所以，我们需要在满足“输入数组每一位都一致”的前提下，调整那些没有被输入显式固定的“潜在选择空间”。

这里我用一个动态规划的思路：

设dp[i]表示，在构造到第i个位置且满足输入前i个元素约束的前提下，第i个元素可能达到的最小值。

转移时，分两种情况：

• 如果a[i]已经给出（即输入数组的这个位置有确定值），那么dp[i] = a[i]，没得选。
• 如果a[i]没有给出（也就是这个位置在输入中不存在，属于我们讨论的前缀范围以外），那么我们可以尝试在dp[i-1]和dp[i-1]+1中取一个较小的合法值。

但你仔细读题会发现，输入的数组是完整的N个元素，不存在“没有给出”的情况。那“末尾最小值”到底在求什么？

我重新想了想题目，发现它其实想表达的是：如果只要求前N-1个位置与输入一致，最后一个位置允许我们自己微调，那么最后一个位置最小可能是多少。换句话说，最后一个位置的输入值只是一个“上限参考”，我们可以尝试把它变小，但前提是前面N-1个元素不变，同时整体仍然满足构造规则。

这个理解对不对呢？考后我跟几个一起笔试的同学对了答案，确认题目就是这个意思。题目原文里“最后一个数的最小值”其实是个陷阱，很多人直接输出a[N-1]，那就丢了分。

怎么求这个最小值？思路是这样的：

设f[i]为“前i个元素与输入完全一致时，第i个元素的最小可能值”。显然：

• f[0] = 0
• 对于i > 0，如果a[i]固定，那么f[i] = a[i]；如果a[i]不固定，则f[i] = max(f[i-1], a[i] - (剩余步数))，这样保证后面还能衔接上。

这个“不固定”的情况，在题目里其实就是最后一个位置。

不过，我后来想起了这道题其实还有一个更简洁的等价说法，也是网上讨论里常见的版本：

给定一个数组A，判断它是否满足A[0]=0且A[i]-A[i-1] ∈ {0, 1}。若满足，则找出所有满足条件的长度为N的序列中，最后一个数的最小值。这里“满足条件”指每一位都不小于A[i]，且依然满足相邻差为0或1的规则。

这样理解的话，A[i]就成了第i个位置的下限约束，而不是精确值。我们需要构造一个尽可能低的合法序列，让每一位都不小于给定的下界。

这个表述我觉得更合理，也更符合动态规划的常规套路。为了让后文清晰，我统一用这个理解来讲。

2.4 最优值DP的状态设计

如果题目是“每位是一个下限约束”，那么问题就变成：

• 给定长度为N的数组A，其中A[0] = 0。
• 要构造序列B，满足：
  • B[0] = 0
  • B[i] - B[i-1] ∈ {0, 1}
  • B[i] >= A[i]对所有的i成立
• 求B[N-1]的最小值。

这个转化非常漂亮，因为它把“判断是否存在合法序列”和“求末尾最小值”统一到了一个框架里。

接下来，状态设计就顺理成章了：

设dp[i]为构造完第i个位置、满足前i+1个约束时，B[i]的最小可能值。

那么考察从dp[i-1]到dp[i]的转移：

• 第i个位置的取值只有两种可能：dp[i-1]或dp[i-1]+1。
• 同时它必须不小于A[i]。
• 为了最小化dp[i]，我们要在dp[i-1]和dp[i-1]+1中选一个大于等于A[i]且尽可能小的值。

用数学表达就是：

base = dp[i-1] candidate1 = base candidate2 = base + 1 dp[i] = min{ x ∈ {candidate1, candidate2} | x >= A[i] }

如果两个candidate都小于A[i]，说明没法满足约束，直接判定非法。

不过这里还有一个细节：如果candidate1 < A[i]且candidate2 >= A[i]，那么dp[i] = candidate2。如果两个都>=A[i]，则取candidate1。如果两个都<A[i]，非法。

用公式简化就是：

dp[i] = dp[i-1] if dp[i] < A[i]: dp[i] = dp[i-1] + 1 if dp[i] < A[i]: return -1 // 非法

这个递推式极其简洁，空间上只需要两个变量滚动更新，时间复杂度O(N)。

2.5 正确性证明概述

为什么这个贪心式DP是对的？

因为序列的每个位置只有两个选择：平走或上台阶。为了最终末尾尽可能小，我们在每个位置都应该“能平走就平走”，只有当下限约束逼着我们往上走一步时，才被迫加1。如果连加1都够不到下限，说明前面的路径已经把高度压得太低，导致后面无法一步追上下限要求，于是判定非法。

这里有一个反直觉的点：在某个位置“主动多跨一步”会不会反而有利于后面的最小值？

答案是：不会。如果你在位置i主动把值抬高，那么在后续所有位置，你都必须至少保持这个高度（因为序列不下降），这只会让末尾值更大或不变。所以在任意位置，能低则低一定是最优的。

这样说可能有点抽象，我举个例子：

A = [0, 0, 0, 2, 2]

用我们的递推：

dp[0] = 0（>= A[0]=0） dp[1] = 0（>= A[1]=0） dp[2] = 0（>= A[2]=0） dp[3]：candidate1=0 < 2，所以尝试candidate2=1，还是<2，非法。

但如果我们早早在第1个位置就把序列抬到1，第2个位置到1，第3个位置到2，其实是可以合法构造的（0,1,1,2,2），末尾值为2。

这说明我们的贪心判定过于严格了。为什么dp[3]会失败？因为前面一直压着0，到第3个位置无论如何一步最多只能到1，无法满足下限2。

那怎么修正？

其实这一步暴露了一个隐藏约束：序列的上升能力是有限的。如果你的下限A[i]很大，而你前面积累的高度太低，光靠最后几步的+1根本追不上。

所以正确的做法，不是在递推时才去检查“这一步够不够”，而是要让dp保留的“最小高度”不能过低。换句话说，我们不仅要记录当前位置能取到的最小值，还要保证这个最小值足够支撑未来的下限。

这个修正思路，我称之为“抬高下界”。具体做法是：dp[i]不再只是贪心平走的最小值，而是在满足“后面能爬上去”前提下的最小可行值。

具体转移时，除了考虑当前位的A[i]，还要用后缀最大值来预判未来的爬升需求。

设suf[i]表示从i到N-1区间内A的最大值。那么在第i个位置，至少需要保证dp[i] + (N-1-i) >= suf[i+1]，因为从i到末尾还剩N-1-i步，每步最多+1，高度必须达到后续的最大下限。

这样dp的转移就要同时考虑两个约束：

dp[i] = max( A[i], dp[i-1], suf[i+1] - (N-1-i) )

但这里要注意，dp[i]还必须满足相邻差不超过1。

所以更准确的递推应该是：

dp[i] = max(A[i], dp[i-1], suf[i+1] - (N-1-i)) dp[i] = min(dp[i], dp[i-1] + 1) // 不能比前一步高超过1

但这两步有前后关系，如果先取max再取min，可能造成矛盾。要解决这个矛盾，我们需要重新思考dp的定义。

2.6 更清晰的解法：可行性区间

其实考场上我绕了好一会，最后换了一个更清晰的视角，就是维护可行高度区间。

定义区间[L, R]，表示第i个位置所有合法构造中，该位置高度可能落在的范围。初始L = R = 0（第0个位置只能是0）。

每往右走一步，高度变化只有0或1，所以新的区间是：

newL = L newR = R + 1

然后加上当前下限约束A[i]，要求高度大于等于它：

newL = max(newL, A[i])

同时，为了保证后续还能爬到未来的高下限，区间还不能太低。假设后面剩余步数为steps = N-1-i，未来最大下限为maxFuture = suf[i+1]，则当前高度至少需要maxFuture - steps，所以：

newL = max(newL, maxFuture - steps)

如果newL > newR，说明区间为空，非法。

最终答案就是处理完所有位置后，区间左端点L（因为要最小高度，取左端点）。

我用这个区间法写的代码，一次通过。复杂度依然是O(N)。

3. 算法实现与代码详解

思路有了，写代码就是水到渠成的事了。下面我用C++写一个完整版本，每一步都会加注释，方便你直接对应到上面的推导。

3.1 判定合法性的预处理

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // 第一步：判断首元素是否为0 if (a[0] != 0) { cout << -1 << endl; return 0; } // 第二步：判断相邻差是否都在{0,1}内 for (int i = 1; i < n; i++) { int diff = a[i] - a[i-1]; if (diff != 0 && diff != 1) { cout << -1 << endl; return 0; } } // 到这里说明给定数组本身已经是合法序列 // 但题目要求的是“能否构造出不同序列并让末尾更小” // 所以进入动态规划求最优值 ... }

这里我先把“可行性判断”独立出来。很多参赛者一上来就套DP，反而把简单问题复杂化。记住：先做可行性判断，再做最优化，这个顺序能帮你省下很多Debug时间。

3.2 后缀最大值预处理

为了在递推中快速查询“未来最大下限”，需要预处理一个后缀最大值数组suf。这个数组的含义是：suf[i]表示a[i]到a[n-1]的最大值。

vector<int> suf(n); suf[n-1] = a[n-1]; for (int i = n-2; i >= 0; i--) { suf[i] = max(a[i], suf[i+1]); }

这段代码没有任何技巧性，但非常关键。没有它，每次都要扫描后续所有元素，复杂度就退化成O(N^2)。

3.3 区间递推求解过程

核心逻辑如下：

int L = 0, R = 0; // 当前高度区间 [L, R] for (int i = 1; i < n; i++) { // 每走一步，R最多+1，L至少不变 R = R + 1; // 约束1：当前高度不能低于输入下限 L = max(L, a[i]); // 约束2：当前高度要足够支撑未来爬升 int steps = n - 1 - i; // 剩余步数 int need = suf[i+1] - steps; // 为了够到未来最大值，当前至少需要的高度 L = max(L, need); // 检查区间是否为空 if (L > R) { cout << -1 << endl; return 0; } } cout << L << endl;

我解释一下为什么L和R要这么更新。

R = R + 1是因为每一步最多只能+1，所以高度上限必然单步递增1。下限L理论上可以不动，但因为有了新的约束，只能往上调，不能往下调。如果L被抬得太高以至于超过R，说明没有任何合法路径可以同时满足所有约束。

举例说明，如果输入是[0, 0, 3]，那处理到第2个位置时：

• 初始L=0, R=0
• 第1个位置：R=1, L=max(0,0)=0, need=suf[2]-1=3-1=2, L=max(0,2)=2
• 此时L=2 > R=1，直接输出-1，判定非法。

这很符合直觉：从0出发，中间位置最高只能到1，而终点要求3，中间隔了2步却只涨了1，永远追不上。

3.4 最终完整代码整合

把上面的片段拼起来，加好头文件和输入输出，就是这样：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (a[0] != 0) { cout << -1 << endl; return 0; } for (int i = 1; i < n; i++) { int diff = a[i] - a[i-1]; if (diff != 0 && diff != 1) { cout << -1 << endl; return 0; } } vector<int> suf(n); suf[n-1] = a[n-1]; for (int i = n-2; i >= 0; i--) { suf[i] = max(a[i], suf[i+1]); } int L = 0, R = 0; for (int i = 1; i < n; i++) { R = R + 1; L = max(L, a[i]); int steps = n - 1 - i; int need = suf[i+1] - steps; L = max(L, need); if (L > R) { cout << -1 << endl; return 0; } } cout << L << endl; return 0; }

3.5 复杂度分析

• 时间复杂度：两次线性扫描，O(N)。
• 空间复杂度：一个后缀数组O(N)。当然也可以用滚动优化省掉，但对于N=10^5级别的数据，开数组毫无压力。

如果笔试时内存限制很严格（比如16MB），N=10^7这种极端情况才需要思考滚动数组。正常校招笔试遇到10^5量级，直接开数组最省心。

4. 实操中的坑与排查技巧

4.1 容易踩的坑：差分检查时用绝对值

有的同学在判断相邻差时喜欢写abs(a[i] - a[i-1]) <= 1，这个其实有问题。

题目要求的是后面比前面大0或1，不允许下降。如果你用绝对值判断，[0, 1, 0]这样的数组也会被判为合法，但实际它不满足规则，因为1到0是下降。所以必须写成diff == 0 || diff == 1，不能取绝对值。

4.2 容易踩的坑：忘记首元素必须为0

有些同学一上来就做差分检查，发现[1, 1, 1, 1]的差分都是0，就认为合法。但题目明确说了首元素始终为0，所以[1, 1, 1, 1]直接判非法。我记得这道题有一个测试点就专门卡这个。

4.3 容易踩的坑：区间更新顺序搞反

区间递推时，如果先把L抬高，再更新R，会导致区间重叠异常。正确的顺序是：先按步数扩展R，再施加约束抬高L。

我自己在考场上就差点搞反。当时我先用a[i]去约束L，然后才给R加1，结果在连续上升序列[0,1,2,3,4,5]上输出错误。后来才意识到，第i步还没走的时候，当前高度不能继承上一步的R+1，必须先走一步再约束。这类区间更新问题，建议每次循环时都先想清楚“现在在哪一步、区间如何扩展、约束如何施加”，别凭手感。

4.4 特殊边界测试

交卷前我构造了几组边界数据自测：

测试[0,0,1,1]时要特别注意：给定数组本身末尾是1，但我们可以构造[0,0,1,1]和[0,1,1,1]两种，末尾最小值是1。但如果输入是[0,0,1,2]，由于第3个位置被固定为2，末尾最小值就是2。

其实换个角度想，这道题的第4个位置如果允许自由选择，它既可以是1也可以是2，但题目给了明确的输入值，所以末尾的最小值就是输入值本身。只有在某些“下限式”理解下，才可能出现更小的构造值。

4.5 和同类题型的对比

这道题和很多经典动态规划题目有相似之处，比如“最长递增子序列”的变体、“跳跃游戏”，还有“摆动序列”。但它们有一个本质区别：这道题的转移只有两种选择，极其简单，难的是“未来约束”的引入方式。后缀最大值的预处理技巧在很多题目里都会用到，比如“需要保证后续容量足够”的调度问题、内存分配问题，思路是相通的。

如果你想深挖，可以去做做LeetCode 55（跳跃游戏）和LeetCode 45（跳跃游戏II），它们也涉及“当前位置能走多远、后面能不能到”的约束推导，只不过那里维护的是可达范围，这里维护的是高度区间。

5. 备选方案与扩展思考

5.1 换个角度：二分答案

区间法是最直接的解法，但还有另一个思路值得了解：二分答案。

既然题目问“末尾最小值”，那直接二分这个最小值，然后检查是否存在合法序列。检查时，从末尾往前倒推：假设末尾值为mid，则前面一步只能是mid或mid-1，同时要满足输入下限a[i]。这个过程可以O(N)完成。

总复杂度O(N log N)，对于N=10^5同样能过。这个方法的好处是思路直观，不需要推导后缀最大值，缺点是代码量稍大，多一个二分模板。如果你在考场上对区间法没把握，二分答案是一个很好的保底方案。

我当时没有用二分，是因为区间法推着推着发现只要维护L和R就行了，写起来更顺手。但如果你对前缀/后缀约束不敏感，二分答案反而更不容易出错。

5.2 从这道题学到的通用方法论

复盘这道题，我觉得最有价值的不是解法本身，而是几个通用的思考套路：

• 先拆题再动手。题目里“最小可能值”这种表述，往往意味着答案不是直接给出的，需要你寻找一个最优构造。先花几分钟明确“什么可变、什么不可变”，能少走很多弯路。
• 可行性判断和最优化分离。先判断输入是否满足基本约束，再做最优化，分步调试时能准确定位错误。
• 区间思维。当某个位置的值不是一个点而是一个范围时，维护下界和上界往往比维护具体值更稳健。这种技巧在很多状态DP里都适用。
• 后缀信息预处理。前向扫描时需要“预知未来”时，后缀数组是常用工具。

5.3 这道题如果用Java写

Java版本的核心思路完全一样，代码结构也差不多。我随手写了一个关键片段：

int L = 0, R = 0; for (int i = 1; i < n; i++) { R = R + 1; L = Math.max(L, a[i]); int steps = n - 1 - i; int need = suf[i + 1] - steps; L = Math.max(L, need); if (L > R) { System.out.println(-1); return; } } System.out.println(L);

Java的Math.max嵌套或者分开写都行，逻辑上没有任何区别。如果是Python，需要注意suf[i+1]在i=n-1时下标越界，所以循环只走到n-2即可。

5.4 考后总结：这类题型的出题逻辑

搜狗的后端笔试出现这种题，其实是有道理的。后端开发里常见的一类问题是“在有限资源下，每一步做一些选择，最后要满足某个全局约束”。比如任务调度中，每个任务有最早开始时间，处理器每个时间片最多处理多少任务，问最早完工时间是多少——和这道题的思想如出一辙。

再比如，服务端限流算法里，令牌桶的容量约束、补充速率约束，其实也可以抽象成类似的模型。某个时刻桶内令牌数不能超过容量，每单位时间补充一个，问你为了在某个时刻有足够令牌，初始时桶里至少要预留多少——这不就是一道“倒推最小可行值”的题吗？

所以说，这种题不是单纯为难你，它是在考察一种抽象建模能力。把业务约束翻译成数学约束，然后用动态规划或贪心求解，这正是后端工程师日常工作的缩影。

6. 写在最后

这道题我考完当天就在备忘录里记了复盘笔记。现在重新整理出来，依然觉得它是一道很有代表性的校招笔试题——看起来简单，做起来容易翻车，翻完车还有深度可以挖。

如果你正在准备后端校招笔试，建议把这道题当作“动态规划入门进阶题”来练，先自己写一遍区间法，再用二分答案写一遍，卡卡时间。两种方法都吃透之后，类似的“前缀/后缀约束最优化”题目，你应该都能举一反三。

另外说个题外话，搜狗2020校招笔试的整体风格偏向基础数据结构加动态规划，难度中等。第二场这道题的正确率据说不高，但它其实并没有用任何高级算法。能在考场冷静下来、舍得花三分钟理清题意的人，基本都能做出来。希望这篇复盘能帮你在下一次笔试里少踩一个坑。