414. Third Maximum Number

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.

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.

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.

Approach 1:

Three pointers

Problem Analysis: LeetCode problem 414 “Third Maximum Number” asks us to find the third largest number in an array. If it doesn’t exist, return the largest number. While this could be solved by sorting, we aim for a more efficient approach.

Solution Approach:

1. Use three variables to track the first, second, and third largest numbers.
2. Iterate through the array, updating these variables as needed.
3. Pay attention to duplicates and special cases.

Time and Space Complexity Analysis:

• Time Complexity: O(n), as we only need to pass through the array once.
• Space Complexity: O(1), as we use a fixed amount of extra space.

题目分析： LeetCode问题414 “Third Maximum Number” 要求我们在数组中找到第三大的数。如果不存在，返回最大的数。这个问题可以通过排序来解决，但是我们希望找到一种更有效的方法。

解题思路：

1. 使用三个变量来追踪第一大、第二大和第三大的数。
2. 遍历数组，更新这三个变量。
3. 注意去重和特殊情况处理。

时间和空间复杂度分析：

• 时间复杂度：O(n)，我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只用到有限的额外空间。

function thirdMax(nums: number[]): number {
    // Initialize three variables to track the largest, second largest, and third largest numbers
    let first = Number.MIN_SAFE_INTEGER, second = Number.MIN_SAFE_INTEGER, third = Number.MIN_SAFE_INTEGER;
    for (let num of nums) {
        // Skip duplicate numbers
        if (num === first || num === second || num === third) continue;
        if (num > first) { // Update the first, second, and third largest numbers
            [third, second, first] = [second, first, num];
        } else if (num > second) {
            [third, second] = [second, num];
        } else if (num > third) {
            third = num;
        }
    }
    return third !== Number.MIN_SAFE_INTEGER ? third : first;
}