LeetCode 414. 第三大的数

2026-01-20 HGNULB 约 9 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 414. 第三大的数

题意分析

给定一个整数数组，要返回其中第三大的「互不相同」的数值；如果去重之后不足三个数，则返回最大值。

「不同的」这三个字是最重要的约束信号：重复出现的数值只占一个名次。也就是说排名建立在数值的去重集合上，而不是数组下标上，[2, 2, 3, 1] 的去重集合是 {3, 2, 1}，第三大是 1 而不是 2。

第二个关键信号藏在数据范围里：元素取值覆盖整个 32 位有符号整数，包含 $-2^{31}$。这意味着任何用类型最小值当「空位哨兵」的写法都会和真实数据撞车，必须改用别的方式表达「这一名还没有值」。

题目还给了进阶要求：时间复杂度 $O(n)$。这排除了「排序后去重取倒数第三」这条路作为最终答案。

边界包括：数组只有一个元素；所有元素都相同；恰好三个不同值；不同值恰好两个（应返回最大值）；以及数组里真的出现 $-2^{31}$。

解法：维护前三大值

核心思路

最直接的写法是排序加去重：把数组升序排好，从后往前找第三个与前一个不同的值。逻辑简单，但代价是 $O(n \log n)$，而且如果不允许改动原数组还要复制一份。另一条常见路子是用有序集合维护，插入时自动去重、超过三个就丢掉最小的，但这引入了额外的容器和对数级的插入开销。

瓶颈很明确：排序把 $n$ 个元素之间的全部相对顺序都算了出来，而题目只关心排在最前面的三个互不相同的值，剩下的比较全是无用功。

观察这个规模差：需要的名次只有三个，是一个与 $n$ 无关的常数。那就可以只用三个变量把这三名扛在手里，扫描时每来一个新数，先看它是不是已经占据了某个名次（是则忽略），否则和三个名次依次比较，插到对应位置并把后面的名次整体顺延。

至于「哪一名还没被填过」，不能用 $-2^{31}$ 之类的哨兵表示，因为它本身是合法数据。改用三个布尔标记 hasFirst、hasSecond、hasThird，把「有没有值」和「值是多少」拆成两件独立的事。

于是扫描过程的不变量是：处理完前缀的任意时刻，带有效标记的 first、second、third 恰好是该前缀中互不相同数值的前三大，且满足 first > second > third；标记为假的名次表示该前缀的不同值个数还不够多。扫描结束时，若 hasThird 为真则 third 就是答案，否则说明不同值不足三个，按题意返回 first。

解题步骤

初始化 first、second、third 为任意值（这里取 0），并把三个存在标记都置为 false。真正表示「空位」的是标记而不是数值，这样才不会和真实的极小值混淆。

遍历数组，对每个 num 先做去重判断：若它等于某个已存在的名次值，直接跳过。这一步保证名次建立在去重集合上，是题面里「不同的」那个词的直接落地。判断必须覆盖三个名次，只比对第一名会让重复值从后门挤进来。

若 !hasFirst || num > first，说明 num 成为新的第一名。顺延要从后往前做：先把 second 连同标记交给 third，再把 first 连同标记交给 second，最后写入 first。顺序反了旧值会被覆盖丢失。

否则若 !hasSecond || num > second，num 成为新的第二名，同样先把 second 顺延给 third，再写入 second。

否则若 !hasThird || num > third，num 直接落在第三名，无需顺延。三个分支用 else if 串联，保证一个元素只被安置一次。

遍历结束后，hasThird 为真则返回 third，否则返回 first。这正是题目对「不足三个不同值」的规定。

以 [2, 2, 3, 1] 走一遍：初始三个名次都无效。第一个 2：不与任何有效名次相等；!hasFirst 成立，走第一分支，third 接过 second 的空位（仍无效），second 接过 first 的空位（仍无效），first = 2 且 hasFirst = true。第二个 2：与 first 相等，判定为已见过，直接跳过——这一步正是把重复值挡在名次之外的地方。接着是 3：不与 first = 2 相等；3 > first，走第一分支，third 接过无效的 second，second 接过 first 得到 2 且 hasSecond = true，first = 3。最后是 1：不等于 3 也不等于 2，hasThird 仍为假所以不参与比较；1 > 3 不成立，1 > 2 不成立，落到第三分支，!hasThird 成立，于是 third = 1，hasThird = true。扫描结束，此时 first = 3、second = 2、third = 1，hasThird 为真，返回 1。

代码实现

class Solution {
    // 只需要维护当前第一大、第二大、第三大三个不同值，不必排序整个数组。
    public int thirdMax(int[] nums) {
        int first = 0;
        int second = 0;
        int third = 0;
        boolean hasFirst = false;
        boolean hasSecond = false;
        boolean hasThird = false;

        for (int num : nums) {
            boolean seen = (hasFirst && num == first)
                    || (hasSecond && num == second)
                    || (hasThird && num == third);
            if (seen) {
                continue;
            }

            if (!hasFirst || num > first) {
                third = second;
                hasThird = hasSecond;
                second = first;
                hasSecond = hasFirst;
                first = num;
                hasFirst = true;
            } else if (!hasSecond || num > second) {
                third = second;
                hasThird = hasSecond;
                second = num;
                hasSecond = true;
            } else if (!hasThird || num > third) {
                third = num;
                hasThird = true;
            }
        }

        if (hasThird) {
            return third;
        }
        return first;
    }
}

func thirdMax(nums []int) int {
    // 只需要维护当前第一大、第二大、第三大三个不同值，不必排序整个数组。
    first, second, third := 0, 0, 0
    hasFirst, hasSecond, hasThird := false, false, false

    for _, num := range nums {
        seen := (hasFirst && num == first) ||
            (hasSecond && num == second) ||
            (hasThird && num == third)
        if seen {
            continue
        }

        if !hasFirst || num > first {
            third = second
            hasThird = hasSecond
            second = first
            hasSecond = hasFirst
            first = num
            hasFirst = true
        } else if !hasSecond || num > second {
            third = second
            hasThird = hasSecond
            second = num
            hasSecond = true
        } else if !hasThird || num > third {
            third = num
            hasThird = true
        }
    }

    if hasThird {
        return third
    }
    return first
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为数组长度。每个元素只被访问一次，去重判断和名次比较各自都是常数次整数比较，与 $n$ 无关，因此满足题目进阶要求。

空间复杂度：$O(1)$，只额外维护三个整型名次和三个布尔标记，不复制数组、不引入任何容器。

关键点总结

当题目只要求「前 $k$ 名」且 $k$ 是一个很小的常数时，用 $k$ 个显式变量替代排序或堆，是把 $O(n \log n)$ 压到 $O(n)$ 的标准动作。

题面里「不同的」三个字决定了必须先判重再排名，而且判重要覆盖全部三个名次；只比对最大值会让重复值从后门挤进来，直接改变答案。

当元素可以取到类型的极值时，绝不能拿极值当哨兵。用独立的布尔标记把「有没有值」和「值是多少」解耦，是这类问题唯一稳妥的写法。

名次顺延必须从后往前赋值，并且值和标记要成对搬运；只搬值不搬标记，会造出「有值但标记为假」或反过来的不一致状态。

面试视角：面试官出这道简单题，八成就是冲着 $-2^{31}$ 这个坑来的。主动说出「元素可以等于 Integer.MIN_VALUE，所以哨兵法不成立，我用存在标记」，基本等于直接过关。

面试视角：追问几乎一定是「把 3 换成 $k$ 怎么办」。要能立刻切换到快速选择或大小为 $k$ 的小顶堆，并说明常数变量的写法在 $k$ 增大后代码量爆炸、不可维护，这体现你知道方法的适用边界。

易错点总结

错误写法：用 Integer.MIN_VALUE 表示「这一名还没填」。用例 [-2147483648, 1, 2] → 真实存在的最小值被误判成空位，程序认为只有两个不同值，返回 2，正确答案是 -2147483648。

错误写法：省掉去重判断，让重复值也参与排名顺延。用例 [2, 2, 3, 1] → 第二个 2 被塞进第二名，最终 third 停在 2，返回 2，正确答案是 1。

错误写法：去重判断只与第一名比较。用例 [3, 2, 2, 1] → 第二个 2 不等于 first = 3 于是被放行，占掉第三名，返回 2，正确答案是 1。

错误写法：第一名分支里只写 second = first，漏掉先把 second 顺延给 third。用例 [1, 2, 3] → 处理 3 时 third 从未被赋值，hasThird 始终为假，返回 first = 3，正确答案是 1。

错误写法：顺延时只搬数值不搬存在标记。用例 [1, 2] → third 拿到了 second 的旧数值但标记被置真，程序误以为已有第三名，返回一个无意义的初始值 0，正确答案是 2。

错误写法：不足三个不同值时返回 second 或直接返回 0。用例 [1, 2] → 返回 1 或 0，题目明确规定这种情况要返回最大值 2。

错误写法：排序后直接取 nums[n - 3]，忘了去重。用例 [2, 2, 3, 1] → 排序得到 [1, 2, 2, 3]，下标 1 上是 2，返回 2，正确答案是 1。

错误写法：用差值比较大小，写成 num - first > 0。用例 [-2147483648, 2147483647] → 两数之差超出 int 范围发生溢出，比较结果反号，名次直接错乱。

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	名次按重复计数而非去重，且 $k$ 不再是常数，需要快速选择或堆
703. 数据流中的第 K 大元素	简单	数据是动态到来的，要用大小固定的小顶堆支持在线插入与查询
628. 三个数的最大乘积	简单	同为一次扫描维护极值，但因负数存在必须同时维护最大三个和最小两个
169. 多数元素	简单	常数空间里维护的是候选值与抵消计数，靠摩尔投票而非名次比较