题目
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).
答案
这题关键点在于maintain 3个var，当新的信息传递进来时 决定reject这个信息，还是准入
如果准入，应该如何处理这3个var的关系。
class Solution {
public int thirdMax(int[] nums) {
// Undefined
if(nums == null || nums.length == 0) return 0;
Integer first_max = null, second_max = null, third_max = null, n = nums.length;
// Maintain three vars, as long as inserting the new number doesn't create duplicates and the new number
// can replace any of the 3 vars
for(int num : nums) {
if(first_max == null || num > first_max) {
third_max = second_max;
second_max = first_max;
first_max = num;
}
else if((second_max == null || num > second_max) && num != first_max) {
third_max = second_max;
second_max = num;
}
else if((third_max == null || num > third_max) && num != first_max && num != second_max) {
third_max = num;
}
}
if(third_max == null) return first_max;
return third_max;
}
}
