LeetCode: Third Maximum Number

LeetCode: 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:

1
2
3
4
5
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

1
2
3
4
5
Input: [1, 2]

Output: 2

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

Example 3:

1
2
3
4
5
6
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(3, Integer::compareTo);

        for (int i : nums) {
            if (queue.contains(i)) continue;
            if (queue.size() < 3 || i > queue.peek()) {
                if (queue.size() > 2) {
                    queue.poll();
                }
                queue.add(i);
            }
        }
        if (queue.size() == 3) return queue.poll();
        while (queue.size() > 1) {
            queue.poll();
        }
        return queue.peek();
    }
}