P4718 最大元素的个数（入门）

解题思路

有一串数，一共 n 个，数字之间可能有重复。题目要求找出这串数中最大的那个元素，并输出它出现的次数。

先看数据范围：n 最大是 10^6，每个数字最大是 10^18。这提醒我们两件事：

1. 数字要用 long long 类型来存，否则会溢出。
2. 数据量很大，读入要快，用 scanf 比用 cin 更稳妥。

这道题有个巧妙之处：我们根本不需要把整串数字都存下来，一边读一边处理就可以了。具体做法是维护两个变量：

• maxv：记录到目前为止遇到的最大值；
• cnt：记录这个最大值到目前为止一共出现了几次。

每读入一个数字 x，分三种情况处理：

• 如果 x 大于 maxv：说明发现了新的更大值，把 maxv 更新为 x，同时 cnt 重置为 1；
• 如果 x 等于 maxv：说明当前最大值又出现了一次，cnt 加 1；
• 如果 x 小于 maxv：它不可能是最大值，直接忽略。

这就好比一个擂台赛：只有比当前擂主更强的选手才能当上新擂主；擂主遇到平手就计数加一；比擂主弱的选手连上场的机会都没有。

读完所有 n 个数之后，cnt 就是最大元素出现的次数。

验证一下样例：7 2 0 7 2 7 1。最大值是 7，它出现了 3 次，所以输出 3。

边界情况：最大值可能连续出现很多次，cnt 可能比较大，用 long long 存储最保险。

参考代码

// 最大元素的个数：找出序列中最大元素并统计它出现的次数
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    long long maxv = -1; // 当前最大值（x>=0，用-1作初始值）
    long long cnt = 0;   // 当前最大值的出现次数
    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld", &x);
        if (x > maxv) { // 发现更大的数，重置计数
            maxv = x;
            cnt = 1;
        } else if (x == maxv) {
            cnt++;
        }
    }
    printf("%lld\n", cnt);
    return 0;
}

复杂度分析

程序从头到尾只扫描了一遍所有数字，每读入一个数字做常数次比较和更新，所以时间复杂度是 O(n)。n 最大是 10^6，只需要约一百万次操作，运行非常快。

空间方面，只用了一个 long long 记录最大值和一个 long long 记录出现次数，外加读入用的临时变量，空间复杂度是 O(1)，完全不随 n 增大，非常节省内存。