找第二大 · 考级冲刺

找最大值只需记一个数；找第二大要同时记住两个：当前最大 mx1 和当前第二大 mx2。关键在更新规则——来了个新数 x：

若 x 比 mx1 还大：原来的最大要退位成第二大，x 当新的最大。
否则若 x 比 mx2 大（但不超过 mx1）：x 顶掉第二大。
再小就不管。

const int NEG = -2000000000;
int mx1 = NEG, mx2 = NEG;
for (int i = 0; i < n; i++) {
    int x = a[i];
    if (x > mx1) { mx2 = mx1; mx1 = x; }   // 最大退位成第二
    else if (x > mx2) mx2 = x;
}
// mx2 就是第二大

一遍扫描， $O (n)$ ，比“先排序再取倒数第二”的 $O (n lo g n)$ 更快。

最容易踩的坑是重复值。数组 3 9 5 9 7 的“第二大”是多少？要看题目怎么定义：

按位置/大小名次（允许重复）：最大是 9，第二大还是 9。上面的代码正好给出 9。
按不同的值（去重后的第二大）：是 7。这时要在 else if 前加一句 if (x == mx1) continue; 跳过与最大相等的数。

考试遇到“第二大”，先确认相等的算不算，再决定要不要跳过重复，否则一半的错都出在这里。