# 0414. Third Maximum Number

https://leetcode.com/problems/third-maximum-number

## Description

Given an integer array `nums`, return _the **third distinct maximum** number in this array. If the third maximum does not exist, return the **maximum** number_.

**Example 1:**

```
**Input:** nums = [3,2,1]
**Output:** 1
**Explanation:**
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.
```

**Example 2:**

```
**Input:** nums = [1,2]
**Output:** 2
**Explanation:**
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.
```

**Example 3:**

```
**Input:** nums = [2,2,3,1]
**Output:** 1
**Explanation:**
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.
```

**Constraints:**

* `1 <= nums.length <= 104`
* `-231 <= nums[i] <= 231 - 1`

**Follow up:** Can you find an `O(n)` solution?

## ac

```java
class Solution {
    public int thirdMax(int[] nums) {
        long max1, max2, max3;
        max1 = max2 = max3 = Long.MIN_VALUE;
        // Set<Integer> set = new HashSet<>();
        // for (int i : nums) set.add(i);

        for (int i : nums) {
            if (i == max1 || i == max2 || i == max3) continue; // skip duplicate
            if (i > max1) {
                max3 = max2;
                max2 = max1;
                max1 = i;
            } else if (i > max2) {
                max3 = max2;
                max2 = i;
            } else if (i > max3) {
                max3 = i;
            }
        }

        if (max3 == Long.MIN_VALUE) return (int)max1;
        else return (int)max3;
    }
}

/*
1) deduplicate, if equal to any of 3 max number, skip; 2) update max1 max2 max3
*/
```
