数列分段

形式化题目

给定 $n$ 个整数组成的数列，把数列划分为若干段，使得每段内的数全部相同，且段与段之间不能再合并，求最少的段数。

思路

数列被划分成极长连续相同段：同一段内相邻数字都相等，段与段交界处相邻数字不同。因此只需线性扫描：

第一个数字一定单独开始一段，答案初始为 $1$ ；
之后每读入一个数字，只要它和前一个数字不同，就说明新的一段从这里开始，答案加一；
全程只保留前一个数字，无需存储整个数列。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:54
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    // 第一个数字一定形成第一段。
    int previous;
    cin >> previous;
    int answer = 1;
    // 相邻数字不同就说明新的一段从这里开始。
    for (int i = 2; i <= n; i++) {
        int current;
        cin >> current;
        if (current != previous) answer++;
        previous = current;
    }
    cout << answer << '\n';
    return 0;
}

复杂度

时间：每个数字只比较一次， $O(n)$ 。
空间：只保存前一个数字， $O(1)$ 。

总结

连续段的边界恰好是“相邻数字不相同”的位置。保留前一个数字即可在线统计，这是入门级“扫描计数”题的标准写法。

目录

形式化题目

思路

代码

复杂度

总结