企业官网建设流程全解析

“2024年题22”是我在某算法训练营里刷到的一道编号题。当时题目描述套了个环形赛车补给站的壳：一圈有 n 个补给站，每个站会给你的“能量”增加或扣除一个数，从任意一站出发，能量在任何时候都不能变成负数，问最多能连续跑过几个站，以及有没有能跑完整圈的起点。初看以为是经典加油站问题的换皮，真做起来才发现它把前缀和、单调栈、破环成链三个东西焊在了一起，稍不注意边界就翻车。这篇复盘把完整推导、代码和踩坑记录都放出来，给正在练算法笔试或者竞赛的朋友做个参考。

1. 题目到底在问什么：题意还原与考点拆解

1.1 场景化题意与数据范围

把故事翻译成数据模型：有一个环形数组 a，长度为 n，下标从 0 到 n-1。从任意下标 i 出发，初始能量为 0，按顺时针方向依次访问 i、i+1、i+2……（越界就取模绕回）。每访问到一个位置 p，能量就加上 a[p]，且访问这个位置之后能量必须仍然大于等于 0，否则挑战在访问这个位置的瞬间失败。

题目要输出两个东西：第一个是最大连续访问站点数，也就是从某个起点出发，最多能成功访问多少站；第二个是“全程可行”的起点数量，即从哪些起点出发能把一整圈 n 个站全部成功访问完。

数据范围是常规竞赛题设置：n 最大到 2e5，a[i] 的绝对值可以到 1e9。这意味着 O(n^2) 的模拟必然超时，必须想办法做到 O(n log n) 甚至 O(n)。我最终用的是 O(n) 的单调栈解法。

这里有一个容易混淆的细节：“最大连续访问站点数”和“全程可行起点数量”并不是同一个问题。前者允许你只跑一段，后者要求你跑完全程。两者都需要在同一个框架下求解，但判定条件略有差异，后面推导时会看到。

1.2 直觉误区与真正的考点

很多人第一眼会把这个题和“环形加油站”划等号，然后下意识准备用贪心找唯一可行起点。实际上两者有本质区别。经典加油站问题只关心“是否存在一个起点能绕一圈”，并且有“总和非负则存在”的强结论；但本题还要求计算“从任意起点出发最长能走多远”，这要求我们对每个起点都算出第一个“能量跌破 0”的位置。

第二个常见误区是只检查区间总和非负。举个例子，数组 [3, -5, 4] 从下标 2 出发，访问 4 之后是 4，访问 3 之后是 7，访问 -5 之后是 2，总和为正，全程可行。但如果数组是 [3, -4, 1]，从下标 2 出发访问 1 之后是 1，访问 3 之后是 4，访问 -4 之后是 0，也刚好可行；可如果顺序变成 [3, 1, -5]，从下标 1 出发访问 1 之后是 1，访问 3 之后是 4，访问 -5 之前已经 4，没问题，但下标 0 出发访问 3 之后是 3，访问 1 后 4，访问 -5 之前 4，也没问题。真正的问题出在类似 [1, -3, 2] 这样的序列：从下标 2 出发，访问 2 后是 2，访问 1 后是 3，访问 -3 之前 3，没问题，但区间总和恰好是 0，如果只判断区间和非负，你会认为任何一个起点都可行，实际从下标 1 出发第一步就 -3 直接失败。所以必须约束的是“所有前缀”而不是最终总和。

这道题真正的考点有三个：一是前缀和建模，把“访问成功”翻译成关于前缀和的不等式；二是单调栈求每个位置右侧第一个“更小前缀和”；三是破环成链处理环形结构。这三个点单拎出来都不难，组合在一起就需要想清楚每一步的边界。

2. 从暴力到线性：两条推导路线

2.1 暴力枚举的写法和复杂度瓶颈

先写一个最直白的暴力版本，复杂度 O(n^2)。逻辑非常简单：枚举每个起点 i，从它开始往环形后面走，维护当前能量 energy，每访问一个站点就累加 a[(i+k)%n]，一旦 energy 变成负数就立刻停止，记录成功走了 k 步。如果成功走满 n 步，就把 count 加一。代码如下：

def brute(a): n = len(a) max_len = 0 count = 0 for i in range(n): energy = 0 step = 0 for k in range(n): energy += a[(i + k) % n] if energy < 0: break step += 1 max_len = max(max_len, step) if step == n: count += 1 return max_len, count

这个代码在小数据下完全正确，但 n=2e5 时内层循环要执行 n 次，总操作量接近 4e10，任何评测机都扛不住。

暴力代码浪费在哪？它把同一个站点反复计算了很多次。比如起点 i 访问到位置 p 时的能量，和起点 i+1 访问到位置 p 时的能量没有直接复用，所有前缀区间都被独立重新算了一遍。要优化，第一步就是把“从 i 走到 p 的总能量变化”变成一个可以通过前缀和 O(1) 查询的东西，第二步才是想办法减少起点的枚举成本。

2.2 前缀和把“可行”变成不等式

破环成链是环形问题的标准手法：把数组复制一份得到 b = a + a，长度为 2n。这样原本绕圈访问 a[i], a[i+1], ..., a[n-1], a[0], a[1], ... 就变成了在 b 上从 i 开始的线性连续访问。因为最多访问 n 个站点，所以把数组复制两遍之后，所有环形访问都能在 b 的一个线性区间里表示。

定义前缀和数组 pre，pre[0] = 0，pre[t] = b[0] + b[1] + ... + b[t-1]，也就是说 pre[t] 表示 b 前 t 个元素的和。那么从起点 i 出发，连续访问到位置 p（包含 p）之后的总能量变化是 pre[p+1] - pre[i]。访问 p 成功的条件就是：

pre[p+1] - pre[i] >= 0

等价于：

pre[p+1] >= pre[i]

进一步，如果从 i 出发出现了第一次失败，那一定存在一个最小的“坏点” j，满足 pre[j] < pre[i]，且这个位置就是某个站点访问完之后的前缀和位置。具体来说，如果访问站点 p 时失败，令 j = p+1，则 pre[j] < pre[i]，而之前所有前缀位置都满足 pre[t] >= pre[i]。

于是题目就变成了一个非常干净的序列问题：对于每个起点 i，在 b 的后续位置中，找到第一个前缀和严格小于 pre[i] 的下标 j。如果找到了，那么从 i 出发最多成功访问 j - i - 1 个站点；如果 j 到 i 的距离已经大于 n，说明第一圈还没走完前都不会失败，也就是能跑完整圈。

可以把这个过程想象成一条海拔曲线：pre 数组就是沿着赛道走出的海拔变化曲线，从起点 i 出发时你的海拔是 pre[i]，只要后面的海拔一直不低于这条水平线，你就安全；第一次“跌到水平线以下”的位置就是坏点。

2.3 单调栈求“下一个更小前缀和”

现在核心变成：对一个长度为 2n+1 的前缀和数组，求每个位置 i 右侧第一个满足 pre[j] < pre[i] 的下标 j。这是个经典问题，用单调栈从右往左扫一遍就能解决。

维护一个栈，栈里存的是前缀和数组的下标，并且从栈底到栈顶，pre 值保持严格递增。从右往左遍历 pre 的下标 i 时，先不断弹出栈顶那些 pre 值大于等于 pre[i] 的下标，因为对于更靠左的位置来说，这些被弹出的下标不仅距离更远，而且高度还不比 pre[i] 低，pre[i] 明显是更优的“潜在更小值候选”。弹出结束后，如果栈不为空，当前栈顶就是 i 右侧第一个 pre 值严格小于 pre[i] 的下标；如果栈空，说明 i 右侧没有更小的 pre 值。最后把 i 压入栈。

这个算法每个下标最多入栈一次、出栈一次，总复杂度 O(n)。它不需要二分，也不需要线段树，代码极短，而且能一次算出所有起点的坏点位置。

值得说明的是，这里比较时必须用“大于等于”作为弹出条件，而不是“大于”。因为题目要求 pre[j] < pre[i] 才算坏点，如果 pre[j] == pre[i]，说明访问到那个位置时能量恰好回到 0，不算失败。弹出大于等于当前值的位置，可以保证栈里保留的是严格递增的前缀和序列，最终栈顶一定是严格更小值。

3. 完整可运行实现与逐段讲解

3.1 Python 实现（单调栈法）

下面是最终通过全部测试的 Python 代码，我加了比较详细的注释。代码核心就三个部分：构造前缀和、单调栈求坏点、统计答案。

def solve(a): n = len(a) b = a + a # 破环成链 m = 2 * n # 前缀和数组，pre[t] 表示 b 前 t 个元素之和 pre = [0] * (m + 1) for i in range(m): pre[i + 1] = pre[i] + b[i] # next_less[i]：i 右侧第一个满足 pre[j] < pre[i] 的下标 j # 用 pre[m] 作为哨兵先放进栈，保证边界处理简单 next_less = [None] * (m + 1) st = [m] for i in range(m - 1, -1, -1): while st and pre[st[-1]] >= pre[i]: st.pop() next_less[i] = st[-1] if st else None st.append(i) max_len = 0 count = 0 for i in range(n): bad = next_less[i] if bad is None or bad - i > n: # 第一个坏点距离超过 n，说明整圈都能走完 count += 1 max_len = max(max_len, n) else: # 坏点之前最后一个成功站点是 bad - 1，成功站点数为 bad - i - 1 max_len = max(max_len, bad - i - 1) return max_len, count

整个算法时间复杂度 O(n)，空间复杂度 O(n)。n=2e5 时在 Python 下运行时间大约几十毫秒到一百毫秒级别，非常稳。

3.2 关键代码行的用意

先看 b = a + a。为什么不复制三份？因为从任何起点出发，只要没能走完一圈就失败，失败位置一定落在 i+1 到 i+n 这个区间内（这里 i 是起点，n 是数组长度），复制两份足够覆盖所有起点的可能失败位置。即使某个起点能走完一圈，我们也只需要知道“坏点距离是否大于 n”，不需要真的知道第二圈哪里失败，复制两份完全够用。

再看不带哨兵的写法会有什么坑。如果直接用 st = []，在扫描到最右侧位置 i = m-1 时，无法把 pre[m] 作为候选比较对象。虽然实际上下标 m 对应的位置根本不需要作为起点，但作为坏点候选它是合法的。比如一个递增的前缀和数组，pre[m] 可能恰好是右侧唯一一个更小的值，虽然它出现得非常远，但距离足够远时结论是“全程可行”，漏掉它会导致 next_less 变成 None，而 None 也会被判成全程可行，所以漏掉不会出错。不过为了逻辑统一，我选择用一个哨兵把 pre[m] 也纳入比较，避免在解释时产生“这里会漏”的疑问。

最后看统计答案的部分。bad 是第一个失败位置对应的前缀和下表。如果 bad - i <= n，说明坏点出现在第一圈之内，此时成功站点是 i, i+1, ..., bad-2 这一段，数量是 bad - i - 1。这个减一特别容易错，我第一次写成了 bad - i，结果所有答案都多 1。原因是 bad 已经对应“访问失败之后的前缀位置”，坏点本身没有被成功访问，数量必须再把失败的那个站点去掉。

3.3 用两个例子验证算法

拿一个稍微复杂的例子手算一遍：a = [3, -1, -1, 2, -5, 1]，n=6。复制成 b，算 pre 数组。肉眼观察从下标 0 出发，访问 3 后能量 3，访问 -1 后 2，访问 -1 后 1，访问 2 后 3，访问 -5 时能量变成 -2 失败，所以最多成功 4 个站点。从下标 5 出发，访问 1 后 1，访问 3 后 4，访问 -1 后 3，访问 -1 后 2，访问 2 后 4，访问 -5 时失败，成功 5 个。所以 max_len 应该是 5，全程可行起点 count 是 0。算法对每个起点求坏点，得到下标 0 的坏点在 pre 下标 5，bad - i = 5，max_len = 4；下标 5 的坏点在 pre 下标 11，bad - i = 6，因为 6 不大于 n=6，不是全程可行，max_len = 11-5-1=5。最终输出 max_len=5, count=0，正确。

再看一个能跑完全程的例子：a = [1, -2, 3, -1]，n=4，总和为 1。暴力验证发现只有从下标 2 出发能完整走完：访问 3、-1、1、-2，最终能量 1，全程非负。算法中 pre[2] = -1，右侧所有前缀和都不小于 -1，bad 不存在，所以 count=1，max_len=4。这也印证了“总和非负时至少存在一个可行性起点，但不是每个起点都可行”。

我强烈建议写一个随机数据对拍程序，把暴力版和优化版跑同样的随机数组，用 assert 对比输出。对拍是刷题最实用的习惯，尤其这种边界多的题，肉眼检查几组样例远远不够。

4. 实战踩坑与常见错误速查

4.1 边界条件为什么会集体翻车

这类题的边界条件特别密集，稍不注意就是连环错。

第一个边界是所有 a[i] 都是负数的情况。此时无论从哪个起点出发，第一步访问就失败，成功站点数应该是 0。我的 max_len 初始值一开始设成 1，直接导致答案错误。把它改成 0 才通过。这个问题看似低级，但在快速写代码时很容易顺手就初始化为 1。

第二个边界是全程走完但第二圈很快失败的场景。比如起点 i 能成功访问 n 个站点，但访问第 n+1 个站点时失败，此时 bad - i 恰好等于 n。很多人会把全程可行的判定写成 bad - i >= n，这是错的。因为 bad - i = n 意味着坏点是第 n 个站点本身，也就是说你根本没有成功访问完 n 个站点，只是访问到第 n 个站点时失败了。必须是 bad - i > n，也就是第一个坏点出现在第 n 个站点之后，才代表第一圈全程成功。

第三个边界是前缀和相等的情况。如果 pre[j] == pre[i]，访问到对应位置时能量恰好是 0，属于成功，不是坏点。单调栈弹出条件必须用 >=，如果写成 >，就会把一个能量刚好归零的位置误判为失败点，导致所有答案偏小。

4.2 环形“复制两份”的隐含陷阱

破环成链是环形题的通用套路，但复制两份之后容易出现下标混乱。比如有人会在 b 上枚举起点 i 时把范围写成 0 到 2n-1，再对每个起点求坏点，这样会让很多起点被重复计算，而且 max_len 可能被算成超过 n 的值。

正确做法是明确“只需要枚举原始起点 0 到 n-1”，因为环形数组一共只有 n 个互不相同的起点，复制两份只是为了给这些起点提供足够长的后续区间。枚举起点时如果遍历到超过 n，其实是在枚举一个已经出现过的起点，统计 count 会重复。

另一个陷阱是 pre 数组的长度。b 的长度是 2n，所以 pre 需要 2n+1 个位置，pre[m] 表示整个 b 的和。写循环时如果 range(m) 而不是 range(m+1)，pre 最后一个位置不会被填入正确的值，导致哨兵比较出错。这类错误很难通过样例发现，因为样例通常很小。

4.3 从 O(n^2) 到 O(n) 的代价

暴力到优化的过程，本质是用空间换时间。pre 数组和 next_less 数组都是 O(n) 空间，n=2e5 时完全没问题，但如果 n 到 1e6，Python 里两个 int 列表大约要 40 到 80 MB，需要留意内存限制。C++ 选手还要注意前缀和可能达到 1e14 量级，必须用 long long，否则在隐藏的大数据上会溢出。

时间复杂度上，单调栈扫描一遍 pre 是 O(2n)，统计答案是 O(n)，总复杂度 O(n)。这里有一个容易忽略的点：虽然求坏点用的是单调栈，但它本质上解决的是“每个位置右侧第一个更小值”，这比滑动窗口更直接。如果你习惯用双指针维护窗口最小值，也可以做，但不能直接套“区间和 >= 0”的普通双指针，因为这里要求所有前缀非负，不是区间和非负。

4.4 常见问题对照表

我把实际调试中遇到的几种现象整理成一个速查表：

这张表我每次做这类题都会对照一遍，尤其是“坏点减一”和“严格大于 n”这两条，属于典型的“想明白很简单，想不明白调一晚上”的坑。

5. 复盘与迁移：这道题背后的通用能力

5.1 和经典加油站、环形最大子段的关系

这道题和经典加油站问题共享同一个前缀和基础，但目标不同。经典加油站只需要找一个可行起点，结论是“总和非负则必然存在”，通常用贪心在 O(n) 内找到那一个起点；而本题要对每个起点求最长可行长度，所以需要保留更多的结构信息。可以说，经典加油站是“一个起点的问题”，本题是“所有起点的问题”。

它和环形最大子段和也有亲缘关系，但差别很大。环形最大子段和允许跨过环边界，求的是最大区间和，不要求中间某个前缀非负；本题要求路径中任何时刻能量非负，是一种更强的约束，后者在动态规划里通常对应“带上下界的前缀和可行性判断”。理解了这几题的区别，以后再遇到类似描述，就能迅速判断该用哪个模型。

5.2 怎么把这个套路迁移到新题

遇到“环形 + 从任意起点出发 + 任意前缀非负”的题，基本可以套用这套流程：先破环成链，再构造前缀和，把可行性转成“前缀和相对高度”问题，最后用单调栈或单调队列求每个起点的第一个坏点。如果题目把初始能量从 0 改成某个正整数 K，不等式会变成 pre[j] - pre[i] + K >= 0，也就是 pre[j] >= pre[i] - K，此时求的是每个 i 右侧第一个小于 pre[i] - K 的位置，仍然可以用类似的单调结构处理，只是阈值变成一条动态水平线，可能需要用带权单调队列。

如果题目要求输出最优起点坐标，而不是只输出长度，那就在更新 max_len 时顺手记录起点下标，逻辑完全一样。如果数据范围更大，比如 n 到 1e6，可以把两个数组合并成一次遍历，用双端队列直接滑动窗口维护窗口内 pre 最小值，也能做到线性时间和更小的空间。

5.3 最后说一点个人体会

我自己在写这道题时，最大的教训不是没想到单调栈，而是被“坏点距离”这个细节绕了很久。第一次通过样例之后，我拿随机数据对拍，发现 count 总是比暴力多，排查了半天才意识到是 >=n 和 >n 的差别。这类边界问题靠肉眼很难看出来，所以我现在刷题养成一个习惯：写完优化版之后，立刻写一个纯暴力函数，用随机小数据对拍几百组，全部通过再提交。这个习惯帮我省下了大量查错时间。如果你也正在刷这类前缀和相关的题目，强烈建议把对拍作为标准流程写进自己的模板里。