What is the main strategy to find the third maximum number in an array?

Track the top three distinct numbers during a single pass or use a set to remove duplicates before selecting the third maximum.

How do duplicates affect the third maximum calculation?

Duplicates must be ignored; repeated values do not count as distinct maxima.

What should I return if the array has fewer than three distinct numbers?

Return the overall maximum number in the array.

Can this problem be solved without sorting the entire array?

Yes, by maintaining three variables for the top distinct numbers or using a min-heap of size three.

Does the array size or value range impact the solution approach?

Yes, but using a single pass or set-based approach efficiently handles arrays up to 10^4 elements and integers within the given bounds.

#414

Easy

auto_awesome数组·排序

LeetCode 题解工作台

第三大的数

给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。示例 1：输入： [3, 2, 1] 输出： 1 解释：第三大的数是 1 。示例 2：输入： [1, 2] 输出： 2 解释：第三大的数不存在, 所以返回最大的数 2 。示例 3：输入： [2, 2, 3…

数组排序

题目描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

lightbulb

解题思路

方法一：一次遍历

我们可以使用三个变量 $m_1$ , $m_2$ , $m_3$ 分别表示数组中的第一大、第二大和第三大的数。初始时，我们将这三个变量都赋值为负无穷大。

然后，我们遍历数组中的每个数，对于每个数，我们将其与 $m_1$ , $m_2$ , $m_3$ 进行比较，根据比较的结果更新这三个变量。具体地，我们遍历数组中的每个数，对于每个数：

如果这个数等于 $m_1$ , $m_2$ , $m_3$ 中的任何一个，我们跳过这个数；
如果这个数大于 $m_1$ ，我们将 $m_1$ , $m_2$ , $m_3$ 的值更新为 $m_2$ , $m_3$ , 这个数；
如果这个数大于 $m_2$ ，我们将 $m_2$ , $m_3$ 的值更新为 $m_3$ , 这个数；
如果这个数大于 $m_3$ ，我们将 $m_3$ 的值更新为这个数。

最后，如果 $m_3$ 的值没有被更新，说明数组中不存在第三大的数，那么我们返回 $m_1$ ，否则我们返回 $m_3$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 nums 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        m1 = m2 = m3 = -inf
        for num in nums:
            if num in [m1, m2, m3]:
                continue
            if num > m1:
                m3, m2, m1 = m2, m1, num
            elif num > m2:
                m3, m2 = m2, num
            elif num > m3:
                m3 = num
        return m3 if m3 != -inf else m1

speed

复杂度分析

指标	值
时间	complexity is O(N) for a single pass or O(N log N) if sorting is used. Space complexity is O(1) for three variables, or O(N) if using a set or heap to store distinct values.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check for duplicate numbers when considering distinct maxima.
question_mark
Confirm behavior when fewer than three distinct numbers exist.
question_mark
Clarify whether negative and large integer bounds are supported.

warning

常见陷阱

外企场景

error
Failing to ignore duplicates and incorrectly counting repeated numbers as distinct.
error
Sorting the entire array unnecessarily, which increases time complexity.
error
Not handling the case where fewer than three distinct numbers exist.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the k-th distinct maximum number in an array, generalizing the approach for any k.
arrow_right_alt
Return both the third maximum and its index in the original array.
arrow_right_alt
Determine the third minimum number with the same array and duplicate constraints.

help

常见问题

外企场景

继续练习

#406 根据身高重建队列 #435 无重叠区间 #378 有序矩阵中第 K 小的元素