搜狗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] 0B[i] - B[i-1] ∈ {0, 1}B[i] A[i]对所有的i成立求B[N-1]的最小值。这个转化非常漂亮因为它把“判断是否存在合法序列”和“求末尾最小值”统一到了一个框架里。接下来状态设计就顺理成章了设dp[i]为构造完第i个位置、满足前i1个约束时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]candidate10 2所以尝试candidate21还是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[i1]因为从i到末尾还剩N-1-i步每步最多1高度必须达到后续的最大下限。这样dp的转移就要同时考虑两个约束dp[i] max( A[i], dp[i-1], suf[i1] - (N-1-i) )但这里要注意dp[i]还必须满足相邻差不超过1。所以更准确的递推应该是dp[i] max(A[i], dp[i-1], suf[i1] - (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[i1]则当前高度至少需要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; vectorint 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]的最大值。vectorint suf(n); suf[n-1] a[n-1]; for (int i n-2; i 0; i--) { suf[i] max(a[i], suf[i1]); }这段代码没有任何技巧性但非常关键。没有它每次都要扫描后续所有元素复杂度就退化成O(N^2)。3.3 区间递推求解过程核心逻辑如下int L 0, R 0; // 当前高度区间 [L, R] for (int i 1; i n; i) { // 每走一步R最多1L至少不变 R R 1; // 约束1当前高度不能低于输入下限 L max(L, a[i]); // 约束2当前高度要足够支撑未来爬升 int steps n - 1 - i; // 剩余步数 int need suf[i1] - 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个位置时初始L0, R0第1个位置R1, Lmax(0,0)0, needsuf[2]-13-12, Lmax(0,2)2此时L2 R1直接输出-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; vectorint 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; } } vectorint suf(n); suf[n-1] a[n-1]; for (int i n-2; i 0; i--) { suf[i] max(a[i], suf[i1]); } 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[i1] - steps; L max(L, need); if (L R) { cout -1 endl; return 0; } } cout L endl; return 0; }3.5 复杂度分析时间复杂度两次线性扫描O(N)。空间复杂度一个后缀数组O(N)。当然也可以用滚动优化省掉但对于N10^5级别的数据开数组毫无压力。如果笔试时内存限制很严格比如16MBN10^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步还没走的时候当前高度不能继承上一步的R1必须先走一步再约束。这类区间更新问题建议每次循环时都先想清楚“现在在哪一步、区间如何扩展、约束如何施加”别凭手感。4.4 特殊边界测试交卷前我构造了几组边界数据自测输入期望输出说明[0]0长度为1直接输出0[0,0,0]0全平走序列[0,1,2]2一路攀升没有下降空间[0,0,1,1]1第3个位置可以保持1不下来末尾最小是1[0,0,3]-1追不上高下限[0,1,0]-1存在下降非法测试[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)对于N10^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[i1]在in-1时下标越界所以循环只走到n-2即可。5.4 考后总结这类题型的出题逻辑搜狗的后端笔试出现这种题其实是有道理的。后端开发里常见的一类问题是“在有限资源下每一步做一些选择最后要满足某个全局约束”。比如任务调度中每个任务有最早开始时间处理器每个时间片最多处理多少任务问最早完工时间是多少——和这道题的思想如出一辙。再比如服务端限流算法里令牌桶的容量约束、补充速率约束其实也可以抽象成类似的模型。某个时刻桶内令牌数不能超过容量每单位时间补充一个问你为了在某个时刻有足够令牌初始时桶里至少要预留多少——这不就是一道“倒推最小可行值”的题吗所以说这种题不是单纯为难你它是在考察一种抽象建模能力。把业务约束翻译成数学约束然后用动态规划或贪心求解这正是后端工程师日常工作的缩影。6. 写在最后这道题我考完当天就在备忘录里记了复盘笔记。现在重新整理出来依然觉得它是一道很有代表性的校招笔试题——看起来简单做起来容易翻车翻完车还有深度可以挖。如果你正在准备后端校招笔试建议把这道题当作“动态规划入门进阶题”来练先自己写一遍区间法再用二分答案写一遍卡卡时间。两种方法都吃透之后类似的“前缀/后缀约束最优化”题目你应该都能举一反三。另外说个题外话搜狗2020校招笔试的整体风格偏向基础数据结构加动态规划难度中等。第二场这道题的正确率据说不高但它其实并没有用任何高级算法。能在考场冷静下来、舍得花三分钟理清题意的人基本都能做出来。希望这篇复盘能帮你在下一次笔试里少踩一个坑。