📝 题目大意

给定一个长度为 $N$ 的整数序列 $A$，其中所有元素互不相同。找出序列中第二大的元素，并输出其在原序列中的位置（下标，从 1 开始计数）。

💡 解题思路

1. 题目分析：题目保证 $N \geq 2$ 且所有 $A_i$ 互不相同，因此最大值和第二大值一定存在且唯一。数据范围 $N \leq 100$ 很小，但更优的算法可以一次遍历完成。

2. 算法推导：

   • 朴素想法：对数组排序，取第二大的值，再扫描原数组找到其下标——但这样需要 $O(N \log N)$ 排序，且会丢失原始位置信息。
   • 更优思路：在一次遍历中同时维护最大值 $b$ 和第二大值 $c$。每读入一个数 $a_i$：
     • 若 $a_i > b$（当前最大值），说明原先的最大值 $b$ 降为第二大值，即 $c \leftarrow b$，然后更新 $b \leftarrow a_i$。
     • 否则，若 $a_i > c$（当前第二大值），直接更新 $c \leftarrow a_i$。
   • 遍历结束后，$c$ 即为整个序列的第二大值。再遍历一次原数组，找到值为 $c$ 的元素的下标 $d$，输出 $d$。

3. 边界与细节：

   • 由于 $A_i$ 互不相同，不会出现最大值和第二大值相等的情况，上述 if-else if 逻辑正确。
   • 当 $N=2$ 时，第一个元素为最大值则第二个元素为第二大值，反之亦然，算法仍正确。
   • 注意变量类型：$A_i \leq 10^9$，在 C++ 中 int 足够（上限约 $2.1 \times 10^9$）。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$。第一遍遍历维护 $b$ 和 $c$ 需要 $O(N)$，第二遍遍历查找下标需要 $O(N)$，总计 $O(N)$。
• 空间复杂度：$O(N)$。存储原数组 $a$ 需要 $O(N)$ 空间。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, b = 0, c = 0, d, a[107];
	// b: 当前最大值, c: 当前第二大值, d: 第二大值所在下标
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		if(a[i] > b)          // 发现比当前最大值更大的数
			c = b, b = a[i];   // 原最大值降为第二大值，更新最大值
		else if(a[i] > c)     // 比最大值小但比第二大值大
			c = a[i];          // 更新第二大值
	}
	for(int i = 1; i <= n; ++i)
		if(a[i] == c) d = i;  // 找到第二大值在原序列中的位置
	cout << d;
	return 0;
}