算法1:双指针-扫描连续段() $O(n)$
//最大值就是最大平均值, 找最大值连续出现的长度
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5+10;
int a[N], n, T;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int mx = -1, res = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
//1. 变量记录的方式
int len = 0;
for (int i = 0; i < n; ++ i) {
if (a[i] == mx) len++; //连续相等就累加
else len = 0; //最大值中断了,清零,从新计数
res = max(res, len);
}
//2. 双指针扫描的方式
// for (int i = 0; i < n; ++ i)
// if (a[i] == mx) {
// int j = i;
// while (a[j] == mx && j < n) j++;
// res = max(res, j-i);
// i = j;
// }
printf("%d\n", res);
}
return 0;
}
算法2:变量维护最大值及其连续长度() $O(n)$
#include <bits/stdc++.h>
using namespace std;
int n, T, x;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int res = 1, mx = -1, len = 0; //len记录当前最大值连续长度 mx最大值 res最大长度
while (n--) {
scanf("%d,", &x);
if (x > mx) mx = x, res = len = 1; //值最大优先,值最大的前提下 长度多
else if (x == mx) len++, res = max(res, len);
else len = 0;
}
printf("%d\n", res);
}
return 0;
}