“2024年题22”是我在某算法训练营里刷到的一道编号题。当时题目描述套了个环形赛车补给站的壳一圈有 n 个补给站每个站会给你的“能量”增加或扣除一个数从任意一站出发能量在任何时候都不能变成负数问最多能连续跑过几个站以及有没有能跑完整圈的起点。初看以为是经典加油站问题的换皮真做起来才发现它把前缀和、单调栈、破环成链三个东西焊在了一起稍不注意边界就翻车。这篇复盘把完整推导、代码和踩坑记录都放出来给正在练算法笔试或者竞赛的朋友做个参考。1. 题目到底在问什么题意还原与考点拆解1.1 场景化题意与数据范围把故事翻译成数据模型有一个环形数组 a长度为 n下标从 0 到 n-1。从任意下标 i 出发初始能量为 0按顺时针方向依次访问 i、i1、i2……越界就取模绕回。每访问到一个位置 p能量就加上 a[p]且访问这个位置之后能量必须仍然大于等于 0否则挑战在访问这个位置的瞬间失败。题目要输出两个东西第一个是最大连续访问站点数也就是从某个起点出发最多能成功访问多少站第二个是“全程可行”的起点数量即从哪些起点出发能把一整圈 n 个站全部成功访问完。数据范围是常规竞赛题设置n 最大到 2e5a[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[(ik)%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这个代码在小数据下完全正确但 n2e5 时内层循环要执行 n 次总操作量接近 4e10任何评测机都扛不住。暴力代码浪费在哪它把同一个站点反复计算了很多次。比如起点 i 访问到位置 p 时的能量和起点 i1 访问到位置 p 时的能量没有直接复用所有前缀区间都被独立重新算了一遍。要优化第一步就是把“从 i 走到 p 的总能量变化”变成一个可以通过前缀和 O(1) 查询的东西第二步才是想办法减少起点的枚举成本。2.2 前缀和把“可行”变成不等式破环成链是环形问题的标准手法把数组复制一份得到 b a a长度为 2n。这样原本绕圈访问 a[i], a[i1], ..., a[n-1], a[0], a[1], ... 就变成了在 b 上从 i 开始的线性连续访问。因为最多访问 n 个站点所以把数组复制两遍之后所有环形访问都能在 b 的一个线性区间里表示。定义前缀和数组 prepre[0] 0pre[t] b[0] b[1] ... b[t-1]也就是说 pre[t] 表示 b 前 t 个元素的和。那么从起点 i 出发连续访问到位置 p包含 p之后的总能量变化是 pre[p1] - pre[i]。访问 p 成功的条件就是pre[p1] - pre[i] 0等价于pre[p1] pre[i]进一步如果从 i 出发出现了第一次失败那一定存在一个最小的“坏点” j满足 pre[j] pre[i]且这个位置就是某个站点访问完之后的前缀和位置。具体来说如果访问站点 p 时失败令 j p1则 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 单调栈求“下一个更小前缀和”现在核心变成对一个长度为 2n1 的前缀和数组求每个位置 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)。n2e5 时在 Python 下运行时间大约几十毫秒到一百毫秒级别非常稳。3.2 关键代码行的用意先看 b a a。为什么不复制三份因为从任何起点出发只要没能走完一圈就失败失败位置一定落在 i1 到 in 这个区间内这里 i 是起点n 是数组长度复制两份足够覆盖所有起点的可能失败位置。即使某个起点能走完一圈我们也只需要知道“坏点距离是否大于 n”不需要真的知道第二圈哪里失败复制两份完全够用。再看不带哨兵的写法会有什么坑。如果直接用 st []在扫描到最右侧位置 i m-1 时无法把 pre[m] 作为候选比较对象。虽然实际上下标 m 对应的位置根本不需要作为起点但作为坏点候选它是合法的。比如一个递增的前缀和数组pre[m] 可能恰好是右侧唯一一个更小的值虽然它出现得非常远但距离足够远时结论是“全程可行”漏掉它会导致 next_less 变成 None而 None 也会被判成全程可行所以漏掉不会出错。不过为了逻辑统一我选择用一个哨兵把 pre[m] 也纳入比较避免在解释时产生“这里会漏”的疑问。最后看统计答案的部分。bad 是第一个失败位置对应的前缀和下表。如果 bad - i n说明坏点出现在第一圈之内此时成功站点是 i, i1, ..., bad-2 这一段数量是 bad - i - 1。这个减一特别容易错我第一次写成了 bad - i结果所有答案都多 1。原因是 bad 已经对应“访问失败之后的前缀位置”坏点本身没有被成功访问数量必须再把失败的那个站点去掉。3.3 用两个例子验证算法拿一个稍微复杂的例子手算一遍a [3, -1, -1, 2, -5, 1]n6。复制成 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 下标 5bad - i 5max_len 4下标 5 的坏点在 pre 下标 11bad - i 6因为 6 不大于 n6不是全程可行max_len 11-5-15。最终输出 max_len5, count0正确。再看一个能跑完全程的例子a [1, -2, 3, -1]n4总和为 1。暴力验证发现只有从下标 2 出发能完整走完访问 3、-1、1、-2最终能量 1全程非负。算法中 pre[2] -1右侧所有前缀和都不小于 -1bad 不存在所以 count1max_len4。这也印证了“总和非负时至少存在一个可行性起点但不是每个起点都可行”。我强烈建议写一个随机数据对拍程序把暴力版和优化版跑同样的随机数组用 assert 对比输出。对拍是刷题最实用的习惯尤其这种边界多的题肉眼检查几组样例远远不够。4. 实战踩坑与常见错误速查4.1 边界条件为什么会集体翻车这类题的边界条件特别密集稍不注意就是连环错。第一个边界是所有 a[i] 都是负数的情况。此时无论从哪个起点出发第一步访问就失败成功站点数应该是 0。我的 max_len 初始值一开始设成 1直接导致答案错误。把它改成 0 才通过。这个问题看似低级但在快速写代码时很容易顺手就初始化为 1。第二个边界是全程走完但第二圈很快失败的场景。比如起点 i 能成功访问 n 个站点但访问第 n1 个站点时失败此时 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 需要 2n1 个位置pre[m] 表示整个 b 的和。写循环时如果 range(m) 而不是 range(m1)pre 最后一个位置不会被填入正确的值导致哨兵比较出错。这类错误很难通过样例发现因为样例通常很小。4.3 从 O(n^2) 到 O(n) 的代价暴力到优化的过程本质是用空间换时间。pre 数组和 next_less 数组都是 O(n) 空间n2e5 时完全没问题但如果 n 到 1e6Python 里两个 int 列表大约要 40 到 80 MB需要留意内存限制。C 选手还要注意前缀和可能达到 1e14 量级必须用 long long否则在隐藏的大数据上会溢出。时间复杂度上单调栈扫描一遍 pre 是 O(2n)统计答案是 O(n)总复杂度 O(n)。这里有一个容易忽略的点虽然求坏点用的是单调栈但它本质上解决的是“每个位置右侧第一个更小值”这比滑动窗口更直接。如果你习惯用双指针维护窗口最小值也可以做但不能直接套“区间和 0”的普通双指针因为这里要求所有前缀非负不是区间和非负。4.4 常见问题对照表我把实际调试中遇到的几种现象整理成一个速查表异常现象可能原因解决办法输出最长长度比实际多 1计算成功站点数时用了 bad - i 而不是 bad - i - 1坏点是失败站点本身不能计入成功数全程可行起点数量偏大判定条件用了 bad - i n改成 bad - i n严格大于全负数数据输出 1max_len 初始化为 1初始化为 0能量恰好归零的位置被当成失败单调栈弹出条件用了 改为 只找严格更小值样例能过但提交 TLE暴力 O(n^2) 没优化换单调栈或单调队列 O(n)大数据答案异常前缀和溢出或 pre 数组长度少了 1C 用 long longPython 确保 pre 长度为 2n1这张表我每次做这类题都会对照一遍尤其是“坏点减一”和“严格大于 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 的差别。这类边界问题靠肉眼很难看出来所以我现在刷题养成一个习惯写完优化版之后立刻写一个纯暴力函数用随机小数据对拍几百组全部通过再提交。这个习惯帮我省下了大量查错时间。如果你也正在刷这类前缀和相关的题目强烈建议把对拍作为标准流程写进自己的模板里。
“2024年题22”是我在某算法训练营里刷到的一道编号题。当时题目描述套了个环形赛车补给站的壳一圈有 n 个补给站每个站会给你的“能量”增加或扣除一个数从任意一站出发能量在任何时候都不能变成负数问最多能连续跑过几个站以及有没有能跑完整圈的起点。初看以为是经典加油站问题的换皮真做起来才发现它把前缀和、单调栈、破环成链三个东西焊在了一起稍不注意边界就翻车。这篇复盘把完整推导、代码和踩坑记录都放出来给正在练算法笔试或者竞赛的朋友做个参考。1. 题目到底在问什么题意还原与考点拆解1.1 场景化题意与数据范围把故事翻译成数据模型有一个环形数组 a长度为 n下标从 0 到 n-1。从任意下标 i 出发初始能量为 0按顺时针方向依次访问 i、i1、i2……越界就取模绕回。每访问到一个位置 p能量就加上 a[p]且访问这个位置之后能量必须仍然大于等于 0否则挑战在访问这个位置的瞬间失败。题目要输出两个东西第一个是最大连续访问站点数也就是从某个起点出发最多能成功访问多少站第二个是“全程可行”的起点数量即从哪些起点出发能把一整圈 n 个站全部成功访问完。数据范围是常规竞赛题设置n 最大到 2e5a[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[(ik)%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这个代码在小数据下完全正确但 n2e5 时内层循环要执行 n 次总操作量接近 4e10任何评测机都扛不住。暴力代码浪费在哪它把同一个站点反复计算了很多次。比如起点 i 访问到位置 p 时的能量和起点 i1 访问到位置 p 时的能量没有直接复用所有前缀区间都被独立重新算了一遍。要优化第一步就是把“从 i 走到 p 的总能量变化”变成一个可以通过前缀和 O(1) 查询的东西第二步才是想办法减少起点的枚举成本。2.2 前缀和把“可行”变成不等式破环成链是环形问题的标准手法把数组复制一份得到 b a a长度为 2n。这样原本绕圈访问 a[i], a[i1], ..., a[n-1], a[0], a[1], ... 就变成了在 b 上从 i 开始的线性连续访问。因为最多访问 n 个站点所以把数组复制两遍之后所有环形访问都能在 b 的一个线性区间里表示。定义前缀和数组 prepre[0] 0pre[t] b[0] b[1] ... b[t-1]也就是说 pre[t] 表示 b 前 t 个元素的和。那么从起点 i 出发连续访问到位置 p包含 p之后的总能量变化是 pre[p1] - pre[i]。访问 p 成功的条件就是pre[p1] - pre[i] 0等价于pre[p1] pre[i]进一步如果从 i 出发出现了第一次失败那一定存在一个最小的“坏点” j满足 pre[j] pre[i]且这个位置就是某个站点访问完之后的前缀和位置。具体来说如果访问站点 p 时失败令 j p1则 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 单调栈求“下一个更小前缀和”现在核心变成对一个长度为 2n1 的前缀和数组求每个位置 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)。n2e5 时在 Python 下运行时间大约几十毫秒到一百毫秒级别非常稳。3.2 关键代码行的用意先看 b a a。为什么不复制三份因为从任何起点出发只要没能走完一圈就失败失败位置一定落在 i1 到 in 这个区间内这里 i 是起点n 是数组长度复制两份足够覆盖所有起点的可能失败位置。即使某个起点能走完一圈我们也只需要知道“坏点距离是否大于 n”不需要真的知道第二圈哪里失败复制两份完全够用。再看不带哨兵的写法会有什么坑。如果直接用 st []在扫描到最右侧位置 i m-1 时无法把 pre[m] 作为候选比较对象。虽然实际上下标 m 对应的位置根本不需要作为起点但作为坏点候选它是合法的。比如一个递增的前缀和数组pre[m] 可能恰好是右侧唯一一个更小的值虽然它出现得非常远但距离足够远时结论是“全程可行”漏掉它会导致 next_less 变成 None而 None 也会被判成全程可行所以漏掉不会出错。不过为了逻辑统一我选择用一个哨兵把 pre[m] 也纳入比较避免在解释时产生“这里会漏”的疑问。最后看统计答案的部分。bad 是第一个失败位置对应的前缀和下表。如果 bad - i n说明坏点出现在第一圈之内此时成功站点是 i, i1, ..., bad-2 这一段数量是 bad - i - 1。这个减一特别容易错我第一次写成了 bad - i结果所有答案都多 1。原因是 bad 已经对应“访问失败之后的前缀位置”坏点本身没有被成功访问数量必须再把失败的那个站点去掉。3.3 用两个例子验证算法拿一个稍微复杂的例子手算一遍a [3, -1, -1, 2, -5, 1]n6。复制成 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 下标 5bad - i 5max_len 4下标 5 的坏点在 pre 下标 11bad - i 6因为 6 不大于 n6不是全程可行max_len 11-5-15。最终输出 max_len5, count0正确。再看一个能跑完全程的例子a [1, -2, 3, -1]n4总和为 1。暴力验证发现只有从下标 2 出发能完整走完访问 3、-1、1、-2最终能量 1全程非负。算法中 pre[2] -1右侧所有前缀和都不小于 -1bad 不存在所以 count1max_len4。这也印证了“总和非负时至少存在一个可行性起点但不是每个起点都可行”。我强烈建议写一个随机数据对拍程序把暴力版和优化版跑同样的随机数组用 assert 对比输出。对拍是刷题最实用的习惯尤其这种边界多的题肉眼检查几组样例远远不够。4. 实战踩坑与常见错误速查4.1 边界条件为什么会集体翻车这类题的边界条件特别密集稍不注意就是连环错。第一个边界是所有 a[i] 都是负数的情况。此时无论从哪个起点出发第一步访问就失败成功站点数应该是 0。我的 max_len 初始值一开始设成 1直接导致答案错误。把它改成 0 才通过。这个问题看似低级但在快速写代码时很容易顺手就初始化为 1。第二个边界是全程走完但第二圈很快失败的场景。比如起点 i 能成功访问 n 个站点但访问第 n1 个站点时失败此时 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 需要 2n1 个位置pre[m] 表示整个 b 的和。写循环时如果 range(m) 而不是 range(m1)pre 最后一个位置不会被填入正确的值导致哨兵比较出错。这类错误很难通过样例发现因为样例通常很小。4.3 从 O(n^2) 到 O(n) 的代价暴力到优化的过程本质是用空间换时间。pre 数组和 next_less 数组都是 O(n) 空间n2e5 时完全没问题但如果 n 到 1e6Python 里两个 int 列表大约要 40 到 80 MB需要留意内存限制。C 选手还要注意前缀和可能达到 1e14 量级必须用 long long否则在隐藏的大数据上会溢出。时间复杂度上单调栈扫描一遍 pre 是 O(2n)统计答案是 O(n)总复杂度 O(n)。这里有一个容易忽略的点虽然求坏点用的是单调栈但它本质上解决的是“每个位置右侧第一个更小值”这比滑动窗口更直接。如果你习惯用双指针维护窗口最小值也可以做但不能直接套“区间和 0”的普通双指针因为这里要求所有前缀非负不是区间和非负。4.4 常见问题对照表我把实际调试中遇到的几种现象整理成一个速查表异常现象可能原因解决办法输出最长长度比实际多 1计算成功站点数时用了 bad - i 而不是 bad - i - 1坏点是失败站点本身不能计入成功数全程可行起点数量偏大判定条件用了 bad - i n改成 bad - i n严格大于全负数数据输出 1max_len 初始化为 1初始化为 0能量恰好归零的位置被当成失败单调栈弹出条件用了 改为 只找严格更小值样例能过但提交 TLE暴力 O(n^2) 没优化换单调栈或单调队列 O(n)大数据答案异常前缀和溢出或 pre 数组长度少了 1C 用 long longPython 确保 pre 长度为 2n1这张表我每次做这类题都会对照一遍尤其是“坏点减一”和“严格大于 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 的差别。这类边界问题靠肉眼很难看出来所以我现在刷题养成一个习惯写完优化版之后立刻写一个纯暴力函数用随机小数据对拍几百组全部通过再提交。这个习惯帮我省下了大量查错时间。如果你也正在刷这类前缀和相关的题目强烈建议把对拍作为标准流程写进自己的模板里。
