LeetCode 414. 第三大的数

约 6 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 阿里
标签
数组 排序

题目描述

✅ 414. 第三大的数

image-20260928224038705

image-20260928224038706

题意分析

按不同数值从大到小排名，返回第三名；如果数组中不足三个不同值，就返回最大值。相同数字出现多次只占一个名次，因此这不是把所有元素排序后直接取倒数第三项。

数组非空，值可以为负，也可以等于 32 位整数的最小值。题目进阶要求线性时间；只需要知道前三个不同值，不必给全部元素排序。

解法：维护前三大值

核心思路

[!blue]

扫描时维护当前已见元素中的第一、第二、第三大不同值。新值若等于某个有效名次，直接跳过，避免同一个数占据多个位置；否则从第一名开始比较，找到它能插入的最高名次。

新值成为第一名时，旧第二顺延到第三，旧第一顺延到第二，再设置新第一；成为第二名时，只把旧第二顺延到第三；成为第三名时直接替换第三。更新从后向前进行，防止先覆盖前面的值后丢失需要顺延的旧数据。

每个名次都有独立的存在标记。初始化的零只是存储占位，只有标记为真才参与比较和去重。顺延时要同时移动数值与标记，这样未凑满三名时不会把占位值误当成真实候选，合法的最小整数也无需充当哨兵。

不在前三名的新值可以丢弃：它不影响当前答案，而随着更多数字出现，前三名的门槛只会提高，不会让这个较小值重新变得必要。因此只对当前三个名次去重就够了，无需全局去重集合。

处理结束时，如果第三名有效就返回它，否则返回第一名。输入非空保证第一名一定存在；不同值不足三个时，题目要求的是最大值，而不是已有的最后一名。

解题步骤

  1. 初始化三个值及各自的存在标记，全部名次初始无效。
  2. 遍历新值，若与任一有效名次相同就跳过。
  3. 依次判断能否进入第一、第二或第三名，按从后向前的顺序同步移动旧值和标记。
  4. 扫描完成，第三名存在就返回第三，否则返回第一。

代码实现

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)$，每个元素只与三个候选进行固定次数的比较。
  • 空间复杂度：$O(1)$，仅保存三个值和三个存在标记，不修改输入。

关键点总结

[!green]

  • 排名按不同值计算，更新名次之前先去重。
  • 插入新候选时从后向前顺延，数值与有效性一起移动。
  • 三个名次足以维护目标，较小的已舍弃值以后也不会进入前三。

易错点总结

[!yellow]

  • 只与第一名比较重复，会让重复第二名占据第三名。
  • 只移动数值却不移动存在标记，可能明明已有三个不同值却仍判断第三名不存在。
  • 用某个合法整数极值表示空名次，会与实际输入混淆；这里用布尔标记区分。
  • 更新第一名后再用它给第二名赋值，会把旧第一名覆盖掉，导致两个名次相同。
  • 不足三个不同值时返回第二名或最小的已有候选，不符合题目要求的最大值。

相似题目

题目 难度 关联与区别
215. 数组中的第K个最大元素 中等 原题按元素重数求第k大，本题先按不同值排名，并在不足三种值时返回最大值。
补充题 151. 字符串中最大的三个不同整数 简单 同样只维护三个不同最大候选，变形题额外从文本解析大整数并返回三个值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/71639474
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！