刷题列表里看到“增减序列”这题时，我一开始是被“思维”二字劝退的。等真正把差分数组那层窗户纸捅破之后，才发现它其实是区间操作类题目里最典型的一个模型——甚至可以说，只要建立起“区间整体变化等于差分端点变化”这个映射，很多同类型题的解法都会变得异常清晰。这道题适合所有正在备战笔试、准备算法竞赛，或者想把差分思想彻底吃透的人。题面一句话就能说完：给定一个长度为 n 的数列，每次可以选一个区间 [l,r]，把它里面所有数同时加 1 或同时减 1，问至少操作多少次能让整个数列变成一个全等的序列；以及在操作次数最少的前提下，最终能得到多少种不同的序列。
这题的精妙之处在于，它看起来像是在问“怎么操作”，实际上答案里完全没有操作方案，只输出两个数字。这两个数字都能用 O(n) 时间算出来，核心素材就是差分数组。下面我把完整的思考过程、推导细节和踩坑记录整理出来，希望能帮你在面对“区间整体增减”这类问题时，第一时间切换视角。
1. 题目复盘与思路转换
1.1 暴力思路为什么必死
刚拿到这道题，很多人会本能地往搜索或者贪心方向想。先看搜索：每次选择一个区间，方向有加一和减一两种，区间数量是 O(n²) 的，操作步数上限又完全没法预估。就算题目给的数据范围只有几十，这个搜索树也大得根本没法看，更不用说竞赛题里 n 通常到 10 万甚至更大。
再看贪心：有人会想，从左到右扫，如果 a[i] 比 a[i+1] 大，就把整个区间 [i+1, n] 减掉差值；如果小，就把 [i+1, n] 加上差值。这种思路在有的区间加问题里能成立，但在这题里会出问题，因为目标值本身没有确定，你每一步操作都会改变后面所有数，而这些改变可能互相抵消。更关键的是，你没有事先找到“最终那个相等值到底是多少”，所有基于“当前最小值/最大值”的贪心都缺少一个稳定锚点。
所以第一个结论是：这题不能从操作序列的角度硬推，必须找到一种数学变换，把“一段区间同时变化”这种看起来很难受的操作，压缩成某种容易计算的形式。差分数组就是这个变换。
1.2 差分数组一登场，区间操作就只剩两个端点
回顾一下差分数组的定义。对于原数组 a[1..n]，构造 b[i] = a[i] - a[i-1]，其中 b[1] = a[1]。这样 a 可以通过对 b 求前缀和还原回去，所以 a 和 b 携带的信息完全等价。
关键看一次区间操作在差分数组里是什么效果。比如 a = [1, 3, 5, 2]，差分数组 b = [1, 2, 2, -3]。现在对区间 [2,3] 整体加 1，a 变成 [1, 4, 6, 2]，再算差分，b 变成 [1, 3, 2, -4]。
对比前后两个 b，你会发现只有两处变了：b[2] 从 2 变成 3，b[4] 从 -3 变成 -4。中间那些差分值完全没动。原因也很直白：区间内部所有数同时加 1，它们之间的相对差不会改变；真正改变的，一个是区间左端点和前面元素的差，另一个是区间右端点后面那个元素和区间末元素的差。
所以一次“区间整体加一”在差分数组中等价于“挑两个位置，一个加一、一个减一”。“区间整体减一”则相反，等价于一个减一、另一个加一。这个转换是整道题的命根子：原本一个影响一整段的操作，变成了只影响两个孤立端点的修改。原来的问题也随之变成：通过反复执行“选两个位置，一个加一、一个减一”的操作，让差分数组中 b[2..n] 这一段的每个值都变成 0。
为什么是 b[2..n]，不是整个 b？因为原数组所有数相等，等价于任意两个相邻数的差都是 0，也就是从第 2 个差分位置开始到第 n 个差分位置全部为 0。b[1] 代表第一个数本身，它可以随便取值，不用归零。
2. 核心推导：两个结论是怎么来的
2.1 归零目标与正负配对
现在的问题非常纯粹：有一堆数字，分布在 b[2..n] 上，有正有负，也有可能是零。你每次可以同时修改两个位置，一个加一、一个减一，目标是让这些数字全部变成零。
怎么操作效率最高？直觉已经给出了答案：让正数和负数尽量互相抵消。因为一次修改同时作用于两个位置，如果一个是正、一个是负，那么这一下操作同时把正数往零方向拉、也把负数往零方向拉，一个操作干了两件事，利用率最高。如果两个都是正数，一个加一另一个减一会导致其中一个更远离零，这种操作完全没必要；如果两个都是负数同理。如果只有一个是零，那等于只解决了一个位置，代价很高。
把 b[2..n] 里面所有正数累加起来，记为 pos；把所有负数的绝对值累加起来，记为 neg。每次正负配对可以让 pos 和 neg 同时减少 1 单位，这种双赢操作最多能做 min(pos, neg) 次。做完之后，正负总有一个先耗尽，剩下的那个还剩 |pos - neg| 个单位，没有同符号的对立面可以抵消了。
剩下的单位怎么办？别忘了我们还有 b[1] 和 b[n+1] 这两个位置。它们不在“必须归零”的范围内，可以拿来当配对对象。一次操作仍然处理一个单位，所以剩下多少就需要多少次操作。总次数就是 min(pos, neg) + |pos - neg|。
这个式子还能化简。如果 pos 更大，min 取 neg，结果是 neg + (pos - neg) = pos；如果 neg 更大，结果是 pos + (neg - pos) = neg。两种情况放到一起，答案就是 max(pos, neg)。到这里，第一问的公式已经出来了。
2.2 最少操作次数为什么是 max(pos, neg)
如果你还想更严谨一点，可以用“下界 + 构造”的方式来证明。下界很好找：一次操作最多只能让正数和负数的总量各减少 1，所以至少需要 max(pos, neg) 次。构造也不难：在正负没有耗尽之前，每次选一个正位置和一个负位置配对；等到一方耗尽后，剩下的操作全部拖着 b[1] 或 b[n+1] 一起做。这样构造出的操作序列恰好就是 max(pos, neg) 次，下界也达到了，所以它一定是最优解。
这里我建议你亲手推一遍小例子，你会发现“最少操作次数”并不只是一个抽象公式。例如 a = [3, 1, 2]，差分数组从第二个位置开始是 [-2, 1]，所以 pos = 1，neg = 2，答案是 max(1, 2) = 2。手动试一下：先对区间 [2,2] 加一，a 变成 [3, 2, 2]；再对区间 [1,1] 减一，a 变成 [2, 2, 2]。正好两次。你还可以试试先对 [2,2] 加一，再对 [2,3] 加一，也能得到 [3, 3, 3]，同样是两次。这说明答案不仅正确，而且操作方案还不止一种。
顺便提一个验证技巧：差分数组有天然性质，从第 2 个位置开始的所有差分值之和正好等于 a[n] - a[1]。所以你在本地调试时，可以顺便打印一下 pos - neg，看它是否等于最后一个数减第一个数。如果不相等，说明统计的差分值漏掉了什么，这个检查能帮你快速定位循环边界的问题。
2.3 种类数为什么是 |pos - neg| + 1
第二问是很多人的丢分点，题面说的是：在最小操作次数前提下，最终得到的数列有多少种不同可能。注意，它不是问操作方案有多少种，而是问最后那个“全都相等的序列”有多少种取值。
继续沿用上面的推导。正负互相抵消的 min(pos, neg) 次操作，对最终基准值没有影响，因为这是一对一的对消，两边都归零。会影响最终结果的，只剩那 |pos - neg| 个单位。它们每个都要和 b[1] 或 b[n+1] 配对。
问题来了：和哪个配对，结果一样吗？不一样。和 b[1] 配对，等价于改变第一个数的“基准”，最终所有相等的值也会跟着变；和 b[n+1] 配对，只相当于把操作区间延伸到数组右边界之外，最终可见的数列值不会改变。你在草稿纸上把逻辑推一遍会发现：这 |pos - neg| 个单位里，如果其中有 k 个选择和 b[1] 配对，那么最终数列的相等值就会相对初始情况移动 k 个单位。k 可以取 0，可以全取，也可以取中间任何数量，所以一共是 |pos - neg| + 1 种可能。
还是用 [3, 1, 2] 来验证。pos = 1，neg = 2，|pos - neg| = 1，答案应当是 2。实际试操作：方案一得到 [2, 2, 2]，方案二得到 [3, 3, 3]，正好两种。再看 [1, 2, 3]，差分是 [1, 1]，pos = 2，neg = 0，最少操作次数 2，种类数 3。手动试一下就知道，最终可以是 [1,1,1]、[2,2,2]、[3,3,3] 三种。公式和直觉完全吻合。
对第二问还可以有一个更直观的理解：最终那个相等值一定落在首尾两个元素之间，种类数等于它们差值的绝对值加一。这个说法在无约束加减的情况下成立，但背后的本质仍然是 k 从 0 取到 |pos - neg| 的过程。
3. 代码实战：三个语言版本与边界处理
3.1 C++ 完整实现：从数组存储到滚动读取
先给一个最清晰的数组实现版本。读入所有数，然后从第二个元素开始逐个算差分。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; long long pos = 0, neg = 0; for (int i = 1; i < n; i++) { long long d = a[i] - a[i - 1]; if (d > 0) pos += d; else neg += -d; } cout << max(pos, neg) << '\n'; cout << llabs(pos - neg) + 1 << '\n'; return 0; }如果数据范围大，不想存完整数组，可以用滚动读取。每次只需要维护前一个数 pre 和当前数 cur，算出差值后更新 pre 即可。这个写法空间复杂度是 O(1)，实际竞赛中更推荐。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; long long pre, cur; cin >> pre; long long pos = 0, neg = 0; for (int i = 1; i < n; i++) { cin >> cur; long long d = cur - pre; if (d > 0) pos += d; else neg += -d; pre = cur; } cout << max(pos, neg) << '\n'; cout << llabs(pos - neg) + 1 << '\n'; return 0; }两个版本核心逻辑完全一样，差别只是读入方式。注意第一份代码的循环是从 i = 1 到 n-1，也就是下标 1 开始，对应原始数组的第 2 个元素，千万不要手滑写成从 0 开始，否则会把第一个数本身当成差分值，整个答案都会错。
3.2 Python 与 Java 实现要点
Python 写起来最简洁，但要注意输入可能有换行和空格混排的情况，直接用 sys.stdin.read().split() 最稳。
import sys data = list(map(int, sys.stdin.read().split())) n = data[0] arr = data[1:] pos = 0 neg = 0 for i in range(1, n): d = arr[i] - arr[i - 1] if d > 0: pos += d else: neg += -d print(max(pos, neg)) print(abs(pos - neg) + 1)Java 版本建议也用 long，因为差分求和很容易突破 int 上限。读入用 Scanner 就够了，数据量更大时可以换 BufferedReader，但核心逻辑不变。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long pre = sc.nextLong(); long pos = 0, neg = 0; for (int i = 1; i < n; i++) { long cur = sc.nextLong(); long d = cur - pre; if (d > 0) pos += d; else neg += -d; pre = cur; } System.out.println(Math.max(pos, neg)); System.out.println(Math.abs(pos - neg) + 1); sc.close(); } }这里最大的一处坑：别用 int。即使单个 a[i] 的范围只有 1e9，n 到 1e5 的时候，pos 和 neg 可能累加到 1e14，int 早就溢出了。我见过不少人提交后 WA，把 int 全改成 long long 立刻 AC。
3.3 数据范围、复杂度与整数溢出细节
这题的复杂度是 O(n) 时间，O(1) 额外空间。n 是输入规模，你必须把所有数都读一遍才能算出所有相邻差，所以 O(n) 已经是理论下界，没有任何可以再优化的空间。
整数溢出为什么这么容易被忽略？因为差分值单个看起来不大，但正数累加是所有上升段的差值总和。考虑一个极端情况：数组从 1e9 一路递增到下一个 1e9，中间 1e5 个位置每次都上升 1e9，那 pos 能达到 1e14，远超 32 位整数的 2.1e9。负数的绝对值同理。所以代码里所有参与累加的变量，全部要用 long long 或等价的 64 位类型。
另外输出时注意：abs 函数在某些编译器里以 int 形式重载，传一个 long long 进去可能被截断。C++ 里保险起见用 llabs，或者调用std::abs并确保参数是 long long，编译器会匹配到正确的重载。Java 的 Math.abs 会自动提升到 long，Python 则没有溢出的概念，这两者相对省心。
4. 常见误区和排查技巧实录
4.1 误区一：把差分数组的第一个位置也算进去
这道题最经典的错误写法是统计时从 a[0] 开始每个元素与前一个的差，逻辑看起来没问题，实际却把 b[1] = a[1] 也当成了一个需要归零的差分值。但 b[1] 根本不用管，它代表第一个元素本身，原数列全都相等也不要求 a[1] 等于 0。
举个例子，a = [5, 5, 5]，本来就全相等，答案应该是 0 和 1。如果你把 b[1] = 5 和后面两个 0 一起算，pos 至少会变成 5，max(pos, neg) 就变成了 5，直接错了。正确做法是循环从第二个元素开始：for i from 1 to n-1，每次算a[i] - a[i-1]。
4.2 误区二：把“数列种类数”理解成“操作方案数”
第二问的表述在很多题解里写得比较简洁，有人会误以为是在问有多少种不同的操作序列能达到最少步数。如果真这么想，答案远不止 |pos - neg| + 1，而且会涉及组合数，复杂度完全不可接受。
题目问的其实是“最终得到的数列有多少种”，而最终数列只由那个共同的相等值决定，所以等价于“最终相等值有多少种不同取值”。每一组最终值对应一种数列，比如最终全是 2 就是一种，最终全是 3 就是另一种。如果你能在草稿纸上把 [3,1,2] 的两种最终结果分别手推出来，这个误解就彻底消失了。
4.3 误区三：负数绝对值累加时粗心出错
用 else 分支算 neg 的时候容易写错符号。比如：
if (d > 0) pos += d; else neg += d; // 错误d 是负数，这样 neg 越加越负，最后 max、abs 全乱套。正确写法是neg += -d，或者neg += abs(d)。如果你不想用分支判断，也可以统一先取绝对值再判断符号，但分支写顺手了就很容易忽略这个负号。可以用表格快速对照：
| 原始差值 d | 正确的统计结果 | 错误写法 | 错误后果 |
|---|---|---|---|
| d > 0 | pos += d | neg += d | 负的差分被加到 neg，导致 neg 变大 |
| d < 0 | neg += -d | neg += |d| 写成 neg += d | neg 变成负数，max 和 abs 计算全错 |
一个排查技巧：统计完 pos 和 neg 后，自己验证一下pos - neg是不是等于a[n-1] - a[0]。这个等式来自差分数组的求和性质，两边不相等就说明统计过程漏了某个位置，或者循环边界写错了。我在本地调试时经常用这个办法快速排除低级错误。
4.4 技巧：用随机小数据做暴力对拍验证
公式推完了，代码写完了，怎么确认万无一失？最实用的办法是小范围暴力对拍。n 取 3 或 4，数组元素取 1 到 3，用 BFS 搜索所有可能的操作状态，求出真实的最少步数和最终种类数，再和公式结果比对。
对拍代码不用写得太复杂，核心思路是维护一个状态集合，每一步尝试所有区间和加减方向，记录首次到达“全体相等”状态的操作次数，然后继续搜索同层级的其他状态，统计有多少个不同的相等值。几组数据跑下来，如果 BFS 结果和公式完全一致，基本就可以放心提交了。这个过程还能顺带帮你加深对差分配对的理解，尤其是当你亲手看到一个差分数组是如何一步步被归零的时候。
5. 模型扩展与同类题目迁移
5.1 变体：每次只能修改相邻两个数
如果把操作限制改成“每次选择相邻两个数，一个加一、一个减一”，原问题就变成一个完全不同的模型。这种操作在差分数组里只改一个位置，相当于把一个单位的“高度”从左边挪到右边。它往往对应“能否通过若干次转移让数组满足某种条件”的判断题，经典套路是先看总和是否守恒，再看是否存在非法状态。
表面上只是操作范围变了，底层思维还是差分。你只要意识到“相邻两数一增一减 = 差分数组单点移动”，很多看起来需要复杂数据结构的问题就会迎刃而解。这也是为什么我建议你先彻底吃透增减序列，因为它是理解这类“操作到底动了什么”的入口。
5.2 变体：给操作加上额外的约束条件
有些题目会加一个限制，比如操作过程中任何位置都不能小于 0，或者最终所有数要相等且不小于某个阈值。加约束之后，上一节的配对公式不能直接用了，因为正负配对的顺序会影响中间状态的合法性。
这时候需要退回到差分视角，按顺序从左到右处理，配合扫描或累加判断。核心仍然是：每次操作对应差分数组上的端点变化，你要保证的只是每个前缀的最低值不越界。如果面试或竞赛里遇到这种带约束的扩展，先回到差分定义，画几组前缀和的图像，通常能比硬模拟快得多地找到思路。
5.3 一张快速判断清单：什么时候该想到差分
根据这几年的刷题经验，我总结了四个比较容易触发“差分思维”的信号，供你参考。
第一，题目里反复出现“区间整体加、减一个值”这样的操作；第二，问的是“最终能否全部相等”或者“全部变为某个值需要多少次”；第三，多个区间操作会影响后续查询，需要快速计算某段区域的累计变化；第四，DAG 或树上的路径操作，需要把路径整体加减转成端点和 LCA 的标记。看到这些特征，优先在草稿纸上把差分数组写出来，哪怕最后用不上，也比空想高效。
回到差分数组本身，它本质上是把“一段区域的连续变化”压缩成“两个端点的离散修改”，和我们平时用前缀和把区间求和变成两个端点的差，思路一脉相承。增减序列这道题之所以经典，就是因为它把这个思想用最纯粹的方式呈现了一遍：没有复杂数据结构，没有乱七八糟的分类讨论，只有一对公式、一次遍历。
最后再分享一个小经验。这个题的推导我最早是在草稿纸上完成的，当时为了验证第二问的“种类数”，我把 [3,1,2] 的所有最短操作路径都列了一遍，列完后发现不同操作路径可能殊途同归，但最终数列种类确实严格等于 |pos-neg|+1。那次手工枚举给我留下的印象比看十遍题解都深。建议你拿到任何一道“思维”标签的题，都先拿最小数据量做一遍手工推导。代码写对只是及格线，能在纸上把为什么讲清楚，才是真正吃透了这道增减序列。
