企业官网建设流程全解析

1. 一次把题面说清楚：平均气温到底要算什么

先说结论：这道题看起来是一道入门级的平均值统计题，实际上换个角度就是“在一个序列里找满足大小关系的最长下标跨度”。我在写 PA8 的时候，第一眼看到“Temperature”这个标题，以为是给一堆温度算个平均数，然后跟阈值比一比就完事了。真的动手测数据才发现，题目要的不是“整段平均”，而是“所有连续子段里，平均气温不低于给定阈值的最长长度”。换句话说，输入是一整年的逐日气温，你要回答的并不是“今年平均多少度”，而是“今年有没有一段持续 N 天以上，平均气温能压在某个标准之上”。

把问题换成人话就是：给定一个长度为 N 的温度序列 A[1..N]，再给一个阈值 T，任意取一段连续的日子 [l, r]，如果这一段的平均温度不低于 T，我们就说这是一段合格的时期。现在要找出所有合格的时期里，最长的那段包含了多少天，找不到就输出 0。

这种描述方式在工程上也有对应场景。比如结构健康监测里，连续若干天的平均温度超过设计值就需要预警；农业上要看“连续多少天日均温超过某个积温线”来决定播种窗口；哪怕是你自己写代码处理传感器数据，也经常会遇到“哎，我要找最长的一段，均值在某个范围里”的需求。所以这道题虽然名字朴素，背后的思路拆开之后能用到不少地方。

我拿到题面后先手算了一个小例子。假设 N = 5，T = 20，温度序列是：

15 21 20 19 22

肉眼扫一遍，最长的合格段是 [21, 20, 19, 22]，合计 82，平均 20.5，长度为 4。有个细节容易漏：如果把 [15, 21, 20, 19, 22] 整个拿来看，平均值是 19.4，不合格，所以答案不能是 5。如果题目不问最长，而是问“有没有长度 4 的合格段”，那你还得先去验证 [15, 21, 20, 19] 或者 [21, 20, 19, 22] 这些子段。

第二个例子用来提醒自己“大于等于”里的等号到底算不算。如果 N = 2，T = 20，温度是：

10 30

那么整段平均值是 (10+30)/2 = 20，正好等于阈值 T。因为题面说的是“不低于”，也就是 ≥，所以这段长度 2 是合法答案。很多人在这个等号上翻车，后面我会专门说边界怎么处理。

这道题的输入规模通常不会太小。我按常见出题习惯估了一下，N 大概可以到 10^5 甚至 10^6，A[i] 和 T 都是整数，温度值还有可能是负数。负数很重要，因为后面做前缀和的时候，负数会打破很多人的直觉，甚至让双指针算法直接失效。

所以严格点说，这道题的核心不是“平均”，而是“长度”。平均值只是给出一个判定条件，真正的挑战在于，你要在众多连续子段里快速找到满足条件的最长一段。

2. 先写暴力：O(N^2) 的枚举为什么能帮后期对拍

拿到题先别急着上高深算法，老老实实把暴力写出来，至少有两个好处：第一，小数据你能靠它得到正确答案；第二，后面写优化版本的时候，可以用它生成随机数据做对拍，找出优化版到底在哪些隐蔽数据上写错了。

暴力思路很简单：枚举左端点 l，再枚举右端点 r，计算区间和，然后判断区间平均值是否 ≥ T。为了不引入浮点数误差，一般不用sum / len >= T这种写法，而是把它改写成sum >= T * len。不过要注意，T 和 len 的乘积可能超出 32 位整数范围，尤其在 Python 里无所谓，在 C++ 里一定要开 long long。

一段暴力代码大概长这样：

def brute(n, T, a): ans = 0 for l in range(n): s = 0 for r in range(l, n): s += a[r] length = r - l + 1 if s >= T * length: ans = max(ans, length) return ans

这个代码做的是对的，但复杂度是 O(N^2)。当 N 到 10^5 的时候，循环次数就是 10^10 这个量级，完全没救；当 N 到 10^6，更是连碰都不能碰。不过它作为对拍基准非常合适，我会在写完优化算法之后，拿它跟优化算法跑几千组随机小数据，逐一核对答案。

还有一个小技巧：暴力代码中判断条件里已经隐含了一个很重要的数学等价关系，我先把结论放在这里，下一节推导。这个等价关系几乎就是整道题的分水岭，看懂了它，后面的一切都是顺水推舟。

你可能觉得“先写暴力再写优化”是多余的流程，但实际上很多竞赛和工程里的坑，恰恰是优化代码写得太顺，结果样例过了，随机数据一跑就挂。暴力就是那个帮你兜底的参考答案。我个人的习惯是只要时间允许，先暴力后优化，再写一个对拍脚本，让两个程序在随机数据上跑一万次。这道题我后来果然靠对拍抓到了一个边界错误，后面会展开讲。

3. 关键转化：把“平均值不低于 T”写成一行前缀不等式

暴力写的没问题，但 O(N^2) 不行，必须想一个能压到 O(N) 的办法。这里最核心的一步，是先把“平均值”这个带除法的条件，改写成“差值和”的条件。

考察一个连续区间 [l, r]，长度记为 len = r - l + 1，区间内温度总和为 S。题目要求：

S / len >= T

两边同时乘以 len，由于 len 一定是正数，不等号方向不变：

S >= T * len

再把右边展开到每一项，就是：

A[l] + A[l+1] + ... + A[r] >= T + T + ... + T

移项合并：

(A[l] - T) + (A[l+1] - T) + ... + (A[r] - T) >= 0

这一步看起来只是代数变形，但它直接把问题从“平均值”变成了“差分后区间和是否非负”。我在这里的做法是，先构造一个新数组 B[i] = A[i] - T，然后问：B 数组里，哪一段连续子数组的和大于等于 0，且长度最长。

这里面还有一个隐藏的好处：不再需要处理除法跟浮点数了。如果直接判断平均值，温度可能是负数，平均值可能是小数，光精度问题就能烦死你。用 B 的区间和，所有数都是整数，比较就是单纯的和 0 比，干净利落。

再进一步，区间和问题天然适合前缀和。定义前缀数组 P[0] = 0，P[i] = P[i-1] + B[i]。那么区间 [l, r] 的和就是 P[r] - P[l-1]。条件就变成：

P[r] - P[l-1] >= 0

也就是：

P[r] >= P[l-1]

到这里，整个问题就变得清晰了：在数组 P 里面，找一对下标 i < j，满足 P[j] >= P[i]，然后让 j - i 最大。注意，这里的 i 对应的是 l-1，j 对应的是 r，所以区间长度就等于 j - i。因为区间至少要有 1 个元素，所以 i 和 j 必须满足 i < j，并且 j 的取值范围是 1 到 N，i 的取值范围是 0 到 N-1。

用刚才的样例验证一下。N = 5，T = 20，A = [15, 21, 20, 19, 22]，B = [-5, 1, 0, -1, 2]，前缀 P 为：

P[0] = 0 P[1] = -5 P[2] = -4 P[3] = -4 P[4] = -5 P[5] = -3

我们要找的是下标跨度最大的 i<j 且 P[j] >= P[i]。肉眼扫，P[5] = -3，P[1] = -5，满足，跨度 4，正是答案。P[5] 和 P[0] 比较，-3 >= 0 不成立，所以不能取整个数组。逻辑完全对上了。

这一步转化之后，题目就不再是“温度”问题了，而是一个“前缀数组上找满足偏序关系的最大下标距离”问题。很多乍看毫无头绪的题，最后都是被这样一层一层“翻译”成简单模型的。也正因为这个原因，我才觉得这道 PA8 值得写一篇比较完整的题解：它把平均数、前缀和、单调性、贪心几样东西一次性串起来了。

4. 用单调栈收编左端点：哪些起点永远当不了答案

现在问题已经变成：给一个数组 P[0..N]，找一对下标 i<j，P[j]>=P[i]，且 j-i 最大。

最朴素的做法还是 O(N^2)：枚举所有左端点 i，枚举所有右侧的 j，判断条件。要优化，我第一反应是“能不能用双指针滑动窗口”。可惜这里有个天真的陷阱：P 数组并不是单调的。比如刚才的例子，P 是 0, -5, -4, -4, -5, -3，中间有升有降。窗口从左往右滑的时候，你没法保证右边界往前扩展时，左边界也可以安全地往前提。双指针要求窗口满足单调性，这里不满足，所以直接放弃。

那怎么办？换一个角度：先分析哪些左端点 i 根本没资格参与答案。

假设有两个下标 i1 和 i2，满足 i1 < i2，而且 P[i1] <= P[i2]。也就是说，i1 在左边，并且前缀值还更小（或者相等）。那么对于任意一个在它们右边的下标 j，只要 P[j] >= P[i2]，必然也有 P[j] >= P[i1]。换句话说，i2 能匹配到的所有 j，i1 都能匹配到。而在长度上，i1 更靠左，于是 j - i1 一定大于 j - i2。那 i2 有什么存在意义？没有，在最优解里，它永远不可能成为左端点。

反过来，如果 i1 < i2 但 P[i1] > P[i2]，那 i1 和 i2 各有各的价值：i1 靠左但是前缀值大，i2 靠右但是前缀值小。到底哪个更好，取决于最终的 j 在哪，所以两个都得留着。

这个逻辑给出一套很干脆的筛选规则：从左往右扫描 P 数组，维护一组候选左端点下标，要求它们的前缀值严格递减。每当遇到一个 P[i]，如果它不比当前最后一个候选的前缀值小，就说明它被已有的某个更左候选“支配”了，可以直接丢掉，不加入候选集合；如果它比最后一个候选的前缀值小，就说明它是一个新的低谷，应该放进候选集合。

具体实现可以用栈。规则就是：

stack = [] for i in range(n + 1): if not stack or P[i] < P[stack[-1]]: stack.append(i)

每步判断用的是严格小于，不是小于等于。为什么要严格？如果 P[i] 和栈顶一样大，那新下标更靠右，前缀值却一样，它也无法在任何答案里胜过更靠左的旧下标，所以同样被支配，没必要入栈。

拿刚才的 P 数组过一遍：

P = [0, -5, -4, -4, -5, -3]

• i=0，P[0]=0，栈空，入栈，栈为 [0]
• i=1，P[1]=-5，-5 < 0，入栈，栈为 [0, 1]
• i=2，P[2]=-4，-4 < -5 不成立，丢弃
• i=3，P[3]=-4，-4 < -5 不成立，丢弃
• i=4，P[4]=-5，-5 < -5 不成立，注意这里是严格小于，相等也丢弃
• i=5，P[5]=-3，-3 < -5 不成立，丢弃

最后候选左端点只剩两个：0 和 1。栈里下标递增，前缀值递减，在示例里恰好形成了一个从 0 到 -5 的下降序列。

这里有个直觉可以分享：你其实是在维护一个“阶梯型”的候选列表。越靠左的候选，前缀值必须越大；越靠右的候选，前缀值必须越小。这样每个候选都代表着一个潜在的“低位买入”机会，越往右买入价越低，但右侧的空间也变少了。最后答案一定是从某个候选出发，向右找到一个足够高的“卖出点”，让两个位置距离最远。

构建候选集合这一步的复杂度是 O(N)，因为每个下标最多入栈一次。

5. 反向扫描挤出最长跨度：主算法与正确性推敲

候选左端点已经筛好了，现在的问题是，怎么配合右端点 j，快速算出最大跨度。

我先把算法流程写出来，然后再解释为什么它是对的。

ans = 0 for j in range(n, 0, -1): while stack and P[j] >= P[stack[-1]]: ans = max(ans, j - stack[-1]) stack.pop()

注意这里 j 的枚举顺序是从右往左，而不是从左往右。设计成这样是有原因的。

假设当前考察某个右端点 j，栈顶是所有候选左端点里最靠右的那一个，记为 top。如果能满足 P[j] >= P[top]，那么对当前这个 j 来说，能跟它匹配的候选里跨度最大的，一定是栈顶，因为栈顶下标最大。所以我们先用 top 更新答案，然后直接把 top 弹出栈，不再留它。

为什么要立刻弹出？这里的思考是：我们已经找到了一个 j，它比 top 的前缀值大。对于更靠左的右端点 j'（也就是 j' < j），即使 P[j'] >= P[top] 依然成立，j' - top 也不会超过 j - top。换句话说，top 能产生的最优跨度已经在当前 j 这里实现了，未来的任何 j' 都不可能用 top 做出更大的答案。所以 top 的使命结束，可以安全弹出。

弹出 top 之后，新的栈顶变成上一个候选。如果 P[j] 仍然能盖过这个更左的候选，说明它在当前 j 这里也能匹配，而且跨度比刚才更长。那我们就继续弹出，继续更新答案。一直弹到栈空，或者 P[j] 小于栈顶前缀值为止。

如果 P[j] 小于栈顶前缀值，说明当前 j 连最靠右的候选都匹配不上，那些更靠左、前缀值更大的候选就更匹配不上。因此当前 j 不是一个有效的右端点，直接跳过，去看 j-1。

用刚才的示例手动跑一遍，P = [0, -5, -4, -4, -5, -3]，栈是 [0, 1]：

• j=5，P[5]=-3，栈顶是下标 1，P[1]=-5。-3 >= -5，更新 ans = 5-1 = 4，弹出 1。此时栈为 [0]，栈顶 P[0]=0。-3 >= 0 不成立，停止。
• j=4，P[4]=-5，栈顶 P[0]=0，-5 >= 0 不成立。
• j=3，P[3]=-4，同样不成立。
• j=2，P[2]=-4，不成立。
• j=1，P[1]=-5，不成立。

最终 ans = 4，跟暴力结果一致。

再试一下等号边界。N=2，T=20，A=[10,30]，B=[-10,10]，P=[0,-10,0]。构建候选栈：P[0]=0 入栈；P[1]=-10 入栈；P[2]=0，不小于 -10，丢弃。栈为 [0,1]。反向扫描：

• j=2，P[2]=0，栈顶 P[1]=-10，0 >= -10，更新 ans=1，弹出 1；现在栈顶 P[0]=0，0 >= 0 成立，更新 ans=2，弹出 0。最终答案是 2，正确。

注意上面第二步用到了等号，这正是我前面提醒过的“不低于”三个字的含义。如果题目改成“严格高于 T”，等号那步就不该更新，写法要换成P[j] > P[stack[-1]]。

这个算法的正确性，用一句话概括就是：候选栈保证每个被弹出的左端点，都已经在自己最长可能的位置上完成了使命；从右往左枚举右端点，保证每次弹出的 left，都是以它能匹配到的最右端点来结算。任何没有弹到、后来被更左端点结算的情况，都不会比已经弹出的答案更好，因为更左意味着跨度更小。

整个过程里，每个下标最多入栈一次，也最多出栈一次，所以反向扫描同样是 O(N)。两部分合起来，总复杂度 O(N)。

6. 代码落地：两个版本的实现与三种必踩的边界

理论讲完，该上代码了。我平时写题解习惯把 Python 和 C++ 都放出来，因为这两种语言在这道题上的写法没有本质区别，但输入输出和整数溢出的处理差异比较大。

先看 Python 版本，重点是大数据输入要用 sys.stdin.buffer.read：

import sys def main(): data = sys.stdin.buffer.read().split() if not data: return n = int(data[0]) T = int(data[1]) a = list(map(int, data[2:2 + n])) pref = [0] * (n + 1) for i in range(1, n + 1): pref[i] = pref[i - 1] + (a[i - 1] - T) stack = [] for i in range(n + 1): if not stack or pref[i] < pref[stack[-1]]: stack.append(i) ans = 0 for j in range(n, 0, -1): while stack and pref[j] >= pref[stack[-1]]: ans = max(ans, j - stack[-1]) stack.pop() print(ans) if __name__ == "__main__": main()

再写一个 C++ 版本，方便那些习惯写 C++ 的朋友：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long T; cin >> n >> T; vector<long long> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<long long> pref(n + 1, 0); for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + (a[i] - T); } vector<int> st; for (int i = 0; i <= n; i++) { if (st.empty() || pref[i] < pref[st.back()]) { st.push_back(i); } } long long ans = 0; for (int j = n; j >= 1; j--) { while (!st.empty() && pref[j] >= pref[st.back()]) { ans = max(ans, (long long)j - st.back()); st.pop_back(); } } cout << ans << "\n"; return 0; }

代码本身不长，但有几个边界问题，我挨个说一下，都是实际写挂了才长记性的地方。

第一个边界是空区间。如果所有温度都低于 T，比如 A = [10, 20]，T = 30，那么不存在任何合格区间，答案应该是 0。暴力代码天然返回 0，优化代码要确保 ans 初始为 0，并且知道自己不会在负数条件下误更新。你可以在纸上跑一下：B = [-20, -10]，P = [0, -20, -30]，候选栈是 [0, 1, 2]，反向扫描时 P[j] 从 -30 一路升到 0，始终盖不过栈顶，ans 保持 0，正确。

第二个边界是 j 的范围必须从 n 到 1，不能从 n 到 0。如果把 j = 0 也纳入扫描，会出现 P[0] >= P[0] 的情况，然后更新 ans = 0 - 0 = 0，虽然不影响最终最大值，但逻辑上不对。更危险的是，如果 P 数组开头有负数栈，j=0 和栈里某些下标比较会算出合法的负数跨度，虽然不会更新 ans，但可能导致你对算法过程理解出偏差。严谨起见，右端点至少是区间右端，而区间长度至少为 1，所以 j 从 1 开始。

第三个边界是整数类型。C++ 里 A[i] 和 T 都可能比较大，A[i] - T 乘以 N 之后很容易超过 int 范围，必须用 long long。我见过不少人在这里没有用 long long，结果小数据全对，一到大数据就出负数，排查半天发现是溢出。Python 不用考虑溢出，这也是我推荐初学者先用 Python 理解算法、再切回 C++ 写高并发场景的原因，不过这只是个人习惯。

还有一个小细节：构建候选栈时用的是pref[i] < pref[stack[-1]]，严格小于。如果温度恰好让前缀值相等，右侧的这个下标会被丢弃。这个设计刚说过，因为相等时它完全被左侧下标支配。别手滑写成小于等于，否则候选栈里会多出一批永远没必要保留的下标，虽然答案一般不会错，但算法就不那么“干净”了。

7. 复杂度总结：这类题目还能往哪边扩展

最后把理论性能做个汇总。构建前缀数组 O(N)，构建候选栈 O(N)，反向扫描 O(N)，所以总时间复杂度 O(N)，空间上只需要前缀数组和栈结构，都是 O(N)。在 N = 10^6 的时候，这个方案跑起来很轻松；在实际验证中，我用随机数据连续跑了几千组，优化版本和暴力版本答案完全一致，只有极少数等号边界场景需要小心核对，最终也都通过了。

我复盘这道题的时候，最大的收获不是那个单调栈写法本身，而是“平均数条件 → 差分前缀数组 → 最大跨度”这条翻译链路。很多题目表面上是一套规则，本质上是另一套规则。一旦你把题面条件改写成前缀数组的不等式，原来搜肠刮肚也想不到的优化，可能就顺着数据结构自然浮现出来了。

这个思路能迁移的地方也不少。比如把阈值 T 变成一个函数，每天阈值不同，B 数组就变成 A[i] - T[i]，剩下的逻辑几乎不用动。再比如题目改成“找出最短的一段，使得平均气温低于某个值”，照样可以翻译成前缀差问题，只是反向扫描和候选栈的构造方向要调整一下。甚至温度换成股价、传感器数值、或任意整数序列，这个模板都能直接用。

如果想进一步挑战自己，可以试试把 N 上限加到 10^7，然后要求空间也压到 O(1) 辅助空间。这时你会发现前缀数组都能省掉，因为候选栈可以用“只记录位置，而不记录前缀值”的方式压缩，或者把前缀值算出来后直接只保留极小值点。不过这属于后话，能把本题的 O(N) 版本写对，PA 系列这道题的核心分就已经拿到了。

我自己的体会是，这类题目最忌讳一上来就背模板。先手动推两遍示例，把前缀不等式写出来，再想为什么单调栈能筛掉冗余候选，最后再去写代码，顺手很多。如果直接把网上搜到的代码复制过来，样例过了也糊里糊涂，下次碰到换皮题还是会卡住。写题解的过程就是把自己曾走过的弯路记录一遍，希望对同样卡在这道题的人有帮助。