易–中 · 边界思维
第二大的数
求最大值你已经会了。第二大只是多一个变量的事 —— 但「所有数都一样」这种情况会把人绊倒。
一句话答案一趟扫描同时记录最大和次大的不同值；所有元素都相同时不存在次大值，输出单词 none。
题目
输入: 第一行一个整数 n(2 ≤ n ≤ 1000)。第二行 n 个用空格隔开的整数(−1000 ≤ ai ≤ 1000)。
输出: 第二大的不同的值。如果所有数都相同,输出 none。
样例:
| 输入 | 输出 |
|---|---|
5 | 7 |
4 | none |
3 | -5 |
难点全在「不同」两个字上。3 9 2 9 7 的答案是 7,不是 9 —— 9 出现了两次,但它仍然只是一个值。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 从你已经会的最大值出发
一个变量 big 存当前最大。再加一个 second。每当新数打败 big,就把旧的 big 降级到 second —— 这一行就是全部技巧。
提示 2 — 两个分支,不是一个
如果 x > big,就移位。否则,若 x 比 big 小、比 second 大,它成为新的 second。正是这个第二分支让重复值无害:当 x == big 时两个分支都不触发,重复的最大值永远不会覆盖第二名。
提示 3 — 这两个变量从什么值开始?
不能是 0。输入可以是负数,0 会伪装成一个根本不存在的「最大值」。用一个低于任何合法输入的哨兵值 -1000000000,最后检查 second 是否还是这个哨兵 —— 如果还是,说明不存在第二大的不同值。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int big = -1000000000, second = -1000000000;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > big) {
second = big;
big = x;
} else if (x < big && x > second) {
second = x;
}
}
if (second == -1000000000) cout << "none" << endl;
else cout << second << endl;
return 0;
}注意你没有做什么:没有存数组,没有排序。一趟遍历、两个变量就完了 —— O(n) 时间、O(1) 空间。同样的「降级移位」形状可以扩展成第三大、两个最小、游戏里的最高两个分数。接下来把这个 O(1) 空间的本事用到一个必须真的重排数组的题上:冒泡排序。
深度解析
为什么这样做对
一趟遍历、两个变量就完了 —— 没有数组,没有排序。这个「降级移位」的形状,是所有 Top-K 问题的骨架。
代价
O(n) 时间、O(1) 空间。先排序再取第二是 O(n log n),还得额外拷一份数据 —— 为了看一张牌把整副牌摊开。
常见错法
- 把
second初始化成 0,输入全是负数时就输出 0 —— 一个数据里根本不存在的答案。 - 只写
x > big一个分支、忘了x < big && x > second,遇到 9 9 7 这种重复值时second会停在上一个最大值上。
下一步
接下来让一条规则自己跑,看它落在哪:冰雹序列。
记住这两句
- 两个变量,一次降级:新王登基时,老王退位成第二。
- 哨兵必须比任何合法输入都小,否则它会伪装成答案。
🐞 这段是错的 —— 点开,亲手让它挂一次
second 从 0 开始 —— 全是负数时它会输出 0
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int big = 0, second = 0; // assumes the input is positive
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > big) {
second = big;
big = x;
} else if (x < big && x > second) {
second = x;
}
}
cout << second << endl;
return 0;
}