顺子区间-腾讯2023笔试(codefun2000)

题目链接
顺子区间-腾讯2023笔试(codefun2000)

题目内容

塔子哥最近喜欢研究顺子，顺子的定义为：排序后相邻两元素的差的绝对值恰好等于 1。
现在有人给塔子哥一个长度为 n 的数组，他问塔子哥有多少长度为 k 的子区间满足：子区间中元素恰好构成一个顺子？但是塔子哥最近没有时间帮他解决这个问题，你能帮帮他吗？
例如，对于数组 [3,7,6,4,5]， 子数组 [4,5] 是一个顺子，子数组[7,6]也是一个顺子。
备注：
子区间可以理解为从原数组中从头部或尾部选择一些元素删掉（或者不删）并保持剩余元素的相对位置不变。

输入描述

第一行两个整数 n 和k ，1≤k≤n≤300000
第二行 n 个整数， a1 ,a2 ,…an,($1\le ai\le 10^6)$

输出描述

输出一个正整数代表答案。

样例1

输入

4 2
1 2 3 4

输出

3

样例1解释

满足条件的区间有 [1,2] 和 [2,3] 还有 [3,4] 。

样例2

输入

6 3
1 3 5 4 6 2

输出

2

样例2解释

满足条件的区间有 [3,5,4] 和 [5,4,6]。

提示

题解1(C++版本)

#include<bits/stdc++.h> using namespace std;  const int N = 3e5 + 10; const int M = 1e6 + 10; int n, k, ans, mx[N], mi[N], a[N], q[N], hmap[M];  void getMax(){ // 维护单调队列的队头保存最大值  	int h = 1, t = 0; 	for(int i = 1; i <= n; i++){ 		while(h <= t && a[q[t]] <= a[i]) t--; // 队尾出队 		q[++t] = i; 		if(i - q[h]+1 > k) h++; 		if(i >= k) mx[i] = a[q[h]]; // 记录最值  	} }  void getMin(){ // 维护单调队列的队头保存最小值  	memset(q, 0, sizeof q); 	int h = 1, t = 0; 	for(int i = 1; i <= n; i++){ 		while(h <= t && a[q[t]] >= a[i]) t--; // 队尾出队 		q[++t] = i; 		if(i - q[h]+1 > k) h++; 		if(i >= k) mi[i] = a[q[h]]; // 记录最值  	} } int main(){ 	memset(mx, 0, sizeof mx); 	memset(mi, 0, sizeof mi); 	memset(hmap, 0, sizeof hmap); 	 	scanf("%d%d", &n, &k); 	for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 	getMax(); getMin(); 	int cnt = 0; 	for(int i = 1; i <= n; i++) { 		hmap[a[i]]++; // hmap[i[：表示i在子区间[i-k+1,i]中出现的次数  		if(hmap[a[i]] == 1) cnt++; // 统计子区间[i-k+1,i]中只出现一次的元素的个数 		if(i < k) continue; // 前k-1个元素，长度<k   		if(cnt == k && mx[i] - mi[i] +1 == k){ // 子区间[i-k+1,i]内的最大值-最小值+1=k,并且子区间[i-k+1,i]内没有重复的数，则该子区间中元素恰好构成一个顺子  			 ans++; 		} 		hmap[a[i - k + 1]]--; // 区间左端点的值出现的次数-1  		if(hmap[a[i - k + 1]] == 0) cnt--; 	} 	printf("%d\n", ans); 	return 0; }