题目：
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.本题是要寻找数组中第三大的数，我们的第一种思路就是使用三个数来保存最大的三个数，便利数组的同时进行修改即可。代码入下：
public int thirdMax1(int[] nums){ Integer max1 = null; Integer max2 = null; Integer max3 = null; for (Integer n : nums) { if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue; if (max1 == null || n > max1) { max3 = max2; max2 = max1; max1 = n; } else if (max2 == null || n > max2) { max3 = max2; max2 = n; } else if (max3 == null || n > max3) { max3 = n; } } return max3 == null ? max1 : max3; }此外，我们还可以使用一个变量来保存数字，一个变量来表示当前保存的是第几大的数字。首先将数组进行排序，然后从数组的最后开始遍历，即从最大的数字开始遍历。代码入下：
public int thirdMax(int[] nums) { int res=Integer.MIN_VALUE, count=0; Arrays.sort(nums); for(int i=nums.length-1; i>=0; i--){ if(res != nums[i]){ res = nums[i]; count++; if(count == 3) break; } } if(count<3) return nums[nums.length-1]; return res; }这两种方法思路差不多，效率也很相近。此外我还看到一种使用priorityQueue的方法，使用优先级队列来保存最大的三个数字。但是因为其本身效率很低，所以代码耗时较长。代码入下：
public int thirdMax2(int [] nums){ PriorityQueue<Integer> pq = new PriorityQueue<>(); Set<Integer> set = new HashSet<>(); for(int num : nums){ if(!set.contains(num)){ pq.offer(num); set.add(num); if(pq.size() > 3) set.remove(pq.poll()); } } if(pq.size()<3) while(pq.size()>1) pq.poll(); return pq.peek(); }