414. Third Maximum Number

O(n) time O(1) space
要确认第三大指的是第三大不同的数还是相同也行

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> s;
        for (long x : nums) {
            s.insert(x);
            if (size(s) > 3) {
                s.erase(begin(s));
            }
        }
        return size(s) < 3 ? *rbegin(s) : *begin(s);
    }
};

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long mx1 = LONG_MIN, mx2 = LONG_MIN, mx3 = LONG_MIN; // 必须是long否则最后无法区分，反例[1, 2, INT_MIN]
        for (long x : nums) {
            if (x > mx1) {
                mx3 = mx2;
                mx2 = mx1;
                mx1 = x;
            } else if (x == mx1) {
                continue;
            } else if (x > mx2) {
                mx3 = mx2;
                mx2 = x;
            } else if (x == mx2) {
                continue;
            } else if (x > mx3) { // 注意不是else，是else if
                mx3 = x;
            }
        }
        return mx3 == LONG_MIN ? mx1 : mx3; // 这一行很重要 因为有可能不同的数不足3个
    }
};