本题要求统计长度为 k 的连续子段中,有多少个恰好构成“完整阶”。根据定义,一个序列 B 是完整阶的充要条件为:
而当 ∣B∣=k 时,第二个条件等价于 max−min=k−1。因此,我们可以通过固定长度的滑动窗口依次检查每一个长度为 k 的子数组,并利用以下两个技巧进行高效判断:
小蓝在学习序列分析时,提出了一种称为“完整阶”的片段。
对于一个序列,若将其按升序排列后,任意相邻两个元素的差值恰好为 1,则称该序列为一个“完整阶”。直观上看,一个完整阶片段包含的整数应当连续且互不相同。因此,序列 B 是完整阶的充要条件为:B 中所有元素互不相同,且最大值与最小值之差等于 ∣B∣−1。
现在给定一个长度为 n 的整数序列 A1,A2,…,An,请你帮小蓝统计有多少个长度为 k 的连续子段恰好构成一个完整阶。
约束:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.