LeetCode 414: Third Maximum Number (One-Pass Top-3 Distinct Tracking)
LeetCode 414ArrayOne PassToday we solve LeetCode 414 - Third Maximum Number.
Source: https://leetcode.com/problems/third-maximum-number/
English
Problem Summary
Given an integer array nums, return the third distinct maximum number. If the third distinct maximum does not exist, return the maximum number.
Key Insight
We only need the top 3 distinct values. Maintain three slots first, second, and third while scanning once. Ignore duplicates before updating slots.
One-Pass Strategy
1) Initialize three empty slots.
2) For each number, skip if equal to an existing slot.
3) If greater than first, shift first→second→third and place it into first.
4) Else if greater than second, shift second→third and place it into second.
5) Else if greater than third, place it into third.
6) Return third if present, otherwise first.
Why It Works (Intuition)
At any time, the three slots store the largest, second largest, and third largest distinct values seen so far. Each update preserves this ordering and distinctness invariant.
Complexity Analysis
Time: O(n) single scan.
Space: O(1).
Common Pitfalls
- Forgetting distinctness (duplicate max values must not consume multiple slots).
- Using primitive min sentinel incorrectly for negative values.
- Returning second max when third does not exist (must return first max).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int thirdMax(int[] nums) {
Long first = null, second = null, third = null;
for (int x : nums) {
long n = x;
if ((first != null && n == first) ||
(second != null && n == second) ||
(third != null && n == third)) {
continue;
}
if (first == null || n > first) {
third = second;
second = first;
first = n;
} else if (second == null || n > second) {
third = second;
second = n;
} else if (third == null || n > third) {
third = n;
}
}
return third == null ? first.intValue() : third.intValue();
}
}func thirdMax(nums []int) int {
var first, second, third *int
same := func(p *int, v int) bool {
return p != nil && *p == v
}
for _, n := range nums {
if same(first, n) || same(second, n) || same(third, n) {
continue
}
if first == nil || n > *first {
third = second
second = first
v := n
first = &v
} else if second == nil || n > *second {
third = second
v := n
second = &v
} else if third == nil || n > *third {
v := n
third = &v
}
}
if third == nil {
return *first
}
return *third
}class Solution {
public:
int thirdMax(vector& nums) {
optional first, second, third;
for (long long n : nums) {
if ((first && n == *first) || (second && n == *second) || (third && n == *third)) {
continue;
}
if (!first || n > *first) {
third = second;
second = first;
first = n;
} else if (!second || n > *second) {
third = second;
second = n;
} else if (!third || n > *third) {
third = n;
}
}
return third ? (int)*third : (int)*first;
}
}; class Solution:
def thirdMax(self, nums: list[int]) -> int:
first = second = third = None
for n in nums:
if n == first or n == second or n == third:
continue
if first is None or n > first:
first, second, third = n, first, second
elif second is None or n > second:
second, third = n, second
elif third is None or n > third:
third = n
return first if third is None else thirdvar thirdMax = function(nums) {
let first = null, second = null, third = null;
for (const n of nums) {
if (n === first || n === second || n === third) continue;
if (first === null || n > first) {
third = second;
second = first;
first = n;
} else if (second === null || n > second) {
third = second;
second = n;
} else if (third === null || n > third) {
third = n;
}
}
return third === null ? first : third;
};中文
题目概述
给定整数数组 nums，返回其中第三大的不同数字。如果不存在第三大的不同数字，则返回最大值。
核心思路
只需维护三个“不同”的最大值槽位：first、second、third。遍历时先过滤重复值，再按大小更新槽位。
一次遍历步骤
1）初始化三个空槽位。
2）遍历每个数，若与已有槽位值相同则跳过。
3）若大于 first，执行 first→second→third 右移并写入 first。
4）否则若大于 second，执行 second→third 右移并写入 second。
5）否则若大于 third，写入 third。
6）若 third 存在返回它，否则返回 first。
正确性直觉
任意时刻三个槽位都保持“当前已扫描元素中的前三个不同最大值”。每次更新都只在满足大小关系时移动并写入，因此不变式始终成立。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 忽略“不同数字”要求，导致重复值占用多个名次。
- 使用不安全的哨兵值处理负数场景。
- 第三大不存在时误返回第二大（应返回最大值）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int thirdMax(int[] nums) {
Long first = null, second = null, third = null;
for (int x : nums) {
long n = x;
if ((first != null && n == first) ||
(second != null && n == second) ||
(third != null && n == third)) {
continue;
}
if (first == null || n > first) {
third = second;
second = first;
first = n;
} else if (second == null || n > second) {
third = second;
second = n;
} else if (third == null || n > third) {
third = n;
}
}
return third == null ? first.intValue() : third.intValue();
}
}func thirdMax(nums []int) int {
var first, second, third *int
same := func(p *int, v int) bool {
return p != nil && *p == v
}
for _, n := range nums {
if same(first, n) || same(second, n) || same(third, n) {
continue
}
if first == nil || n > *first {
third = second
second = first
v := n
first = &v
} else if second == nil || n > *second {
third = second
v := n
second = &v
} else if third == nil || n > *third {
v := n
third = &v
}
}
if third == nil {
return *first
}
return *third
}class Solution {
public:
int thirdMax(vector& nums) {
optional first, second, third;
for (long long n : nums) {
if ((first && n == *first) || (second && n == *second) || (third && n == *third)) {
continue;
}
if (!first || n > *first) {
third = second;
second = first;
first = n;
} else if (!second || n > *second) {
third = second;
second = n;
} else if (!third || n > *third) {
third = n;
}
}
return third ? (int)*third : (int)*first;
}
}; class Solution:
def thirdMax(self, nums: list[int]) -> int:
first = second = third = None
for n in nums:
if n == first or n == second or n == third:
continue
if first is None or n > first:
first, second, third = n, first, second
elif second is None or n > second:
second, third = n, second
elif third is None or n > third:
third = n
return first if third is None else thirdvar thirdMax = function(nums) {
let first = null, second = null, third = null;
for (const n of nums) {
if (n === first || n === second || n === third) continue;
if (first === null || n > first) {
third = second;
second = first;
first = n;
} else if (second === null || n > second) {
third = second;
second = n;
} else if (third === null || n > third) {
third = n;
}
}
return third === null ? first : third;
};
Comments