题目大意

给定一个长度为 n 的序列，问如何将该序列归类为最少的连续递增序列。连续递增序列满足：对于序列中的任意 i，满足 a[i] = a[i-1] + 1。

注意原序列不能被任意打乱

题解：贪心 + 哈希表

致歉

注意本题的相对顺序是无法改变的，详情请见小明补充的样例4

题目内容

某媒体处理服务负责接收来自多个媒体发送源的媒体包，并根据收到的媒体包进行媒体渲染处理。当前有这样一个需求：给定收到的媒体包序列号列表，计算发送该媒体包的最少发送源个数。

约束：

1.任意媒体包序列号$seqs[i]$满足：$0≤seqs[i]≤65535$

2.网络上没有重传媒体包，即：同一个发送源发送的媒体包序列号不会重复，且序列号每次加$1$(不考虑回绕问题，$65535$是发送源发送的最后一个媒体包序列号)；如果收到的，媒体包序列号不满足该规则，说明这些媒体包必然来自于多个发送源。

$3$. $1≤seqs.length()≤10^5$

输入描述

第一行：$seqs$列表长度$n$

第二行：$seqs$列表元素，元素之间通过空格隔开

输出描述

最少媒体包发送源个数

样例1

输入

11
1 2 3 4 5 6 7 8 9 10 10

输出

2

说明

媒体包发送源$1$:$1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$

媒体包发送源$2$:$10$

媒体发送源个数为$2$，因此输出$2$

样例2

输入

5
65535 0 1 2 3

输出

2

说明

媒体包发送源$1$:$65535$

媒体包发送源$2$:$0\ 1\ 2\ 3$

媒体发送源个数为$2$，因此输出$2$

样例3

输入

18
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10

输出

2

说明

媒体包发送源$1$:$1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$

媒体包发送源$2$:$2\ 3\ 4\ 5\ 6\ 7\ 8\ 9$

媒体发送源个数为$2$，因此输出$2$

样例4

输入

8
2 2 2 2 1 1 1 1

输出

8

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写