Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Use three variables, first, second and third, initialized with Long.MIN_VALUE. Now update accordingly. Remember when you update the maximum number, the second and third maximum number should also be updated. So as when updating the second number.

public int thirdMax(int[] nums) {
        long first = Long.MIN_VALUE, second = Long.MIN_VALUE, third = Long.MIN_VALUE;
        for (int n : nums) {
            if (n > first) {
                third = second;
                second = first;
                first = n;
            } else if (first > n && n > second) {
                third = second;
                second = n;
            } else if (second > n && n > third) {
                third = n;
            }
        }
        return third > Long.MIN_VALUE ? (int)third : (int)first;
    }