Question:

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]
  3. Output: 1
  5. Explanation: The third maximum is 1.
  1. Input: [1, 2]
  3. Output: 2
  5. Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
  7. Input: [2, 2, 3, 1]
  9. Output: 1
  11. Explanation: Note that the third maximum here means the third maximum distinct number.
  12. Both numbers with value 2 are both considered as second maximum.

Solution:

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var thirdMax = function(nums) {
  6.     // 使用辅助空间
  7.     let first = nums[0],
  8.         second = Number.MIN_SAFE_INTEGER,
  9.         third = Number.MIN_SAFE_INTEGER;
  10.     for ( let i = 1; i < nums.length; i++ ) {
  11.         // 如果比第一个数大
  12.         if ( nums[i] > first ) {
  13.             third = second;
  14.             second = first;
  15.             first = nums[i]
  16.         } else if ( nums[i] > second && nums[i] < first ) {
  17.             third = second;
  18.             second = nums[i];
  19.         } else if ( nums[i] > third && nums[i] < second ) {
  20.             third = nums[i];
  21.         } else {
  22.             continue;
  23.         }
  24.     }
  25.     return third === Number.MIN_SAFE_INTEGER ? first : third
  26. };

Runtime: 72 ms, faster than 48.48% of JavaScript online submissions for Third Maximum Number.