LC.414 ｜ 第三大的数 ｜ 数组 ｜ 一次遍历维护三个最大值（去重）

输入：非空整数数组nums（可能包含重复元素）。

要求：返回数组中第三大的不同数字；如果不存在第三大的不同数字，则返回数组中的最大值。

输出：整数（第三大或最大值）。

思路：

题眼是“第三大”指的是不同数字的第三大，所以必须去重。

用一次遍历维护三个变量：

• max1：当前最大值
• max2：当前第二大（不同值）
• max3：当前第三大（不同值）

初始化都为LLONG_MIN，避免数组里有INT_MIN时冲突。

遍历每个元素v时：

1. 先去重：如果v等于max1/max2/max3，直接跳过。
2. 然后把v放进这三个槽位里（类似插入排序的三格版）：
   • v > max1：整体后移：max3=max2, max2=max1, max1=v
   • 否则如果v > max2：max3=max2, max2=v
   • 否则如果v > max3：max3=v

遍历结束：

• 如果max3还是没被填过（仍为LLONG_MIN），说明不足三个不同数，返回max1
• 否则返回max3

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

classSolution{public:intthirdMax(vector<int>&nums){longlongmax1=LLONG_MIN,max2=LLONG_MIN,max3=LLONG_MIN;for(intx:nums){longlongv=x;// 去重：只统计“不同数字”的排名if(v==max1||v==max2||v==max3)continue;if(v>max1){max3=max2;max2=max1;max1=v;}elseif(v>max2){max3=max2;max2=v;}elseif(v>max3){max3=v;}}return(max3==LLONG_MIN)?(int)max1:(int)max3;}};