#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,a[105];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--){
    	if(a[n]!=a[i]){
    		printf("%d",a[i]);
    		break;
		}
	}
    return 0;
}

📝 题目大意

给定 $N$ 个整数，找出其中不是最大值的整数里最大的那个（即严格第二大的值）。题目保证输入不会全部相等，答案一定存在。

💡 解题思路

1. 题目分析：$N \le 100$，$A_i \le 100$，数据范围极小。关键条件是"答案一定存在"，意味着至少有两个不同的数，因此第二大的数必然存在。
2. 算法推导：
   • 先用 max_element 找出整个数组的最大值 maxVal。
   • 初始化 secondMax = -1（因为 $A_i \ge 1$，$-1$ 比所有元素都小，可用于哨兵）。
   • 遍历数组，对于每个元素 $x$，若 $x < \text{maxVal}$ 且 $x > \text{secondMax}$，则更新 secondMax。
   • 最终 secondMax 即为严格小于最大值的最大元素。
3. 边界与细节：最大值可能出现多次（如样例 3），遍历时用 < 而非 <= 来排除所有等于最大值的元素，确保找到的是"严格第二大"。初始化 secondMax = -1 的安全性由 $A_i \ge 1$ 保证。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，两次遍历数组。
• 空间复杂度：$O(N)$，存储输入数组。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    // 找到数组中的最大值
    int maxVal = *max_element(A.begin(), A.end());
    // 哨兵初始化，由于 A_i >= 1，-1 比所有元素都小
    int secondMax = -1;
    for (int x : A) {
        // 严格小于最大值，且大于当前候选值，则更新
        if (x < maxVal && x > secondMax) {
            secondMax = x;
        }
    }
    cout << secondMax << endl;
    return 0;
}