LeetCode 1380题《Lucky Numbers in a Matrix矩阵中的幸运数》放在题库里就是一道不起眼的Easy题。但我在刷它的时候连续交了好几版执行用时一直徘徊在100ms上下排名惨不忍睹。后来回头一梳理才发现这道题根本不用那么绕它的核心其实是一个很漂亮的数学性质想明白了之后代码甚至可以压缩到几行。这篇文章就把我从“暴力遍历”到“最优解法”的完整思路、踩过的坑、以及从这道简单题里延伸出来的经验都整理出来分享给大家。这道题适合谁看如果你正在刷LeetCode、准备面试或者只是单纯想在矩阵题里找点手感这篇文章都可以给你一些参考。我会把每一种解法的推导过程、复杂度、以及为什么这么写都讲清楚。尤其是那个“幸运数最多只有一个”的隐藏性质很多讨论区里的高赞答案也是一句话带过但真正理解它之后你会发现整个题目瞬间从“查表题”变成了“数学题”。1. 题目到底在问什么幸运数的定义与直觉1.1 从题目描述说开去先看题目的原始定义给你一个 m x n 的矩阵如果一个元素 matrix[i][j] 同时满足两个条件那它就是幸运数它是第 i 行的最小值它是第 j 列的最大值。换句话说这个数在自己的行里“最小”在自己所在的列里“最大”。这听起来像什么就像一个人在班级里是某个科目倒数第一但在全校这个科目里又是正数第一听起来像是“错位”的评价体系里冒出来的一个奇怪交集。实际场景里这种数当然很少见所以题目才叫“幸运数”。我在读题的时候第一反应是这不就是双重条件判断吗每行找最小每列找最大然后看有没有重合的元素。思路本身不复杂但要注意一个容易被忽略的细节——题目明确说了矩阵里的所有元素是互不相同的distinct。这个条件非常关键它直接决定了解法的复杂度。1.2 一个容易忽略的隐含条件幸运数最多只有一个我第一次做这题的时候直接按照“可能不止一个幸运数”的思路去写用哈希表存了一堆候选值结果返回的时候还要考虑顺序把自己绕得不轻。后来重新读题才发现题目里已经埋好了线索所有元素不同而幸运数同时是“行最小”和“列最大”在互不相同的约束下幸运数最多只有一个。为什么这里可以给一个比较直观的证明思路。假设存在两个幸运数 x 和 y它们的位置分别在 (i1, j1) 和 (i2, j2)。因为 x 是第 i1 行的最小值而 y 也在这一行中的某个位置如果 i1 和 i2 相同那 x 和 y 在同一行两者又都是行最小值元素互不相同的话就矛盾了。同理因为 y 是第 j2 列的最大值那么 x 所在的第 i1 行、第 j2 列这个位置的值一定不比 y 大也不比 x 小最后会推出 x 和 y 必须相等。既然元素互不相同那 x 和 y 只能是同一个位置、同一个值。这个性质带来的最大简化就是最后返回的结果要么是空列表要么是只包含一个元素的列表。代码写起来可以放心大胆地直接 return 单个值不用考虑“多个幸运数按什么顺序返回”这种问题。2. 从暴力到优雅三种解法思路拆解2.1 第一反应暴力遍历逐个验证最容易想到的办法就是二重循环遍历每一个格子再花额外的时间去检查它是不是当前行的最小值、当前列的最大值。伪代码差不多是这样遍历矩阵中的每个元素 matrix[i][j]检查第 i 行里有没有比它更小的数检查第 j 列里有没有比它更大的数如果两个条件都满足直接返回。复杂度是多少矩阵是 m 行 n 列遍历每个格子是 O(mn)检查一次行要 O(n)检查一次列要 O(m)所以总时间复杂度是 O(mn*(mn))。如果题目给的矩阵是 50x50那也就是 5050100 250000 次操作现代机器跑起来秒钟级别完全没问题。但你要是在 LeetCode 上直接交这么一版大概率会发现自己排到了赛博朋克级别的“末端”。不是算法错了是这个思路太“厚道”了属于用计算量换思考量。如果矩阵规模变成 1000x1000暴力法的操作数就变成 10^9 级别普通的 OJ 环境可能直接给你一个超时。所以暴力法适合什么场景适合你在头脑发热、或者刚学完循环想练手的时候。真正刷题时一眼能看出暴力解但最好再逼自己想一想有没有空间换时间的做法2.2 角色互换先算行最小与列最大暴力法的问题在于每检查一个格子都要重复扫描整行整列。这个“重复扫描”完全没有必要。我们可以提前把所有行的最小值、所有列的最大值都算好之后再拿着这份“预计算表”去判断每个格子。具体的做法有两种变体我分别说一下。第一种是“数组存值法”开两个数组 rowMin[m] 和 colMax[n]第一遍遍历矩阵把 rowMin[i] 填成第 i 行的最小值第二遍遍历矩阵把 colMax[j] 填成第 j 列的最大值。第三遍遍历所有格子如果某个元素同时等于 rowMin[i] 和 colMax[j]那它就是幸运数。第二种是“集合相交法”把所有的行最小值塞进一个哈希集合 rowMinSet把所有的列最大值塞进另一个哈希集合 colMaxSet最后求这两个集合的交集。因为幸运数要同时满足“是行最小值”和“是列最大值”所以它必然同时出现在两个集合里交集里就是答案。这两种变体本质是一样的都是把“每次判断时重复扫描”变成“提前扫描一遍存起来”。时间复杂度从 O(mn(mn)) 降到了 O(m*n)内存开销 O(mn)。对于这道题来说这个复杂度已经非常够用了。2.3 更优雅的数学结论max(行最小值) 与 min(列最大值)如果你刷题刷得多了会慢慢养成一种直觉凡是“既是集合 A 又是集合 B”的题很多时候可以转化为“A 的某个极值和 B 的某个极值比较”。这道题就是典型。既然幸运数最多只有一个我其实不需要真的遍历所有格子去查交集只需要看两个数所有行最小值里的最大值记作 maxRowMin所有列最大值里的最小值记作 minColMax。如果 maxRowMin minColMax这个相等的值就是幸运数如果不相等矩阵里就没有幸运数。为什么这个结论成立我用自己的方式理解了一遍确实能讲通。假设存在某个幸运数 x它自己是某一行 i 的最小值那么 x 一定不小于这一行里的所有数所以 x 至少不会小于所有行最小值的最大值也就是说 x maxRowMin。另一方面 x 又是某一列 j 的最大值那么 x 一定不大于这一列里的所有数所以 x 不会大于所有列最大值的最小值也就是说 x minColMax。如果 x 真的存在那它必须同时满足这两个不等式那就必须有 maxRowMin x minColMax。同时因为 x 是行最小值之一所以 x maxRowMin又因为 x 是列最大值之一所以 x minColMax。把这两个方向一夹就能推出 x maxRowMin minColMax。反过来如果 maxRowMin minColMax那这个等号成立的位置就是那个同时满足两个条件的幸运数。这个结论的好处是你只需要扫描两遍矩阵分别求出 rowMin 数组和 colMax 数组然后再做一个求数组极值的操作就能得到答案连第三遍遍历矩阵都省了。代码可以写得非常干净也特别适合在面试时展示你对问题的理解深度。2.4 三种方案横向对比为了更直观地看出差别我整理了一张对比表。这里的时间和空间复杂度都是按 m 行 n 列来算的。解法时间复杂度空间复杂度代码量推荐程度暴力遍历O(mn(mn))O(1)少不推荐预处理行最小/列最大O(m*n)O(mn)中推荐max(行最小值) 与 min(列最大值)O(m*n)O(mn)少很推荐我个人在实际刷题时会选择第三种写法因为它把题目背后那个“最多只有一个幸运数”的性质用到了极致。但我也建议你至少把第二种写法练熟因为预处理思路在后续刷矩阵类题目时很常用比如旋转矩阵、蛇形遍历、岛屿问题都会用到“先扫一遍记录信息”的技巧。3. 代码实现与实测表现3.1 C实现一套顺手且不容易写错的写法我用 C 写的最顺手的版本是“预处理数组 双重遍历查值”逻辑清晰不容易写错。class Solution { public: vectorint luckyNumbers(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); vectorint rowMin(m, INT_MAX); vectorint colMax(n, INT_MIN); // 第一遍统计每一行的最小值 for (int i 0; i m; i) { for (int j 0; j n; j) { rowMin[i] min(rowMin[i], matrix[i][j]); } } // 第二遍统计每一列的最大值 for (int j 0; j n; j) { for (int i 0; i m; i) { colMax[j] max(colMax[j], matrix[i][j]); } } // 第三遍找到同时满足两个条件的元素 for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] rowMin[i] matrix[i][j] colMax[j]) { return {matrix[i][j]}; } } } return {}; } };这里要注意初始化的细节。rowMin 要初始化为 INT_MAX因为我们要不断取 min初始值必须是一个“大数”colMax 要初始化为 INT_MIN因为要不断取 max初始值必须是一个“小数”。很多初学者喜欢把 rowMin 初始化成 matrix[i][0]也不是不行但写成 INT_MAX / INT_MIN 可以避免处理空行空列的边界问题代码更稳。3.2 Python实现三行解决问题的技巧Python 写这种矩阵题最大的优势就是列表推导式。如果你用了“集合相交法”代码能精简到三种解法里最少的样子。class Solution: def luckyNumbers(self, matrix: List[List[int]]) - List[int]: row_mins {min(row) for row in matrix} col_maxs {max(col) for col in zip(*matrix)} return list(row_mins col_maxs)拆开解释一下。第一行min(row) for row in matrix得到每一行的最小值外面套一个集合推导式得到一个集合 row_mins。第二行zip(*matrix)的作用是“解压缩”矩阵的行把矩阵的列变成行相当于做了转置然后对每一列取 max得到每一列的最大值集合 col_maxs。第三行直接用集合的交集因为幸运数要同时满足两个条件所以正好是交集。这个版本为什么可以这么精简核心还是因为题目保证了元素互不相同所以 row_mins 和 col_maxs 的交集最多只有一个元素转换成 list 返回没有任何歧义。如果你面试时敢写出这种写法面试官多半会觉得你对 Python 的掌握很熟练。3.3 关于“耗时100”的一点实测感受题目标题里写的“耗时100”指的是我第一版暴力解法在 LeetCode 上提交后的执行用时恰好一百毫秒出头。放在很多年前的老评测机上这个成绩还能看但放到现在讨论区里一堆 0ms、4ms 的 C 解法我这个 100ms 就显得很扎眼。为什么暴力法会这么慢关键在于“重复扫描”。矩阵里每个格子都要做一次行内比较和列内比较而且这些比较完全没有利用已计算的信息。比如你检查完 (0, 0) 发现它是第 0 行的最小值等到检查 (0, 3) 的时候第 0 行的最小值你已经知道了但暴力法还是会重新把第 0 行扫一遍。这就是明显的重复劳动。优化之后用预处理法再提交执行用时基本能降到几毫秒到十几毫秒。这个差距恰恰说明了“先观察数据特点再决定算法”的重要性。其实 LeetCode 上显示的耗时本身会受到网络、服务器负载、测试用例波动的影响没必要特别迷信那几毫秒的差距但复杂度从 O(mn(mn)) 降到 O(m*n)这个优化是实打实的。3.4 边界条件单行、单列、1x1矩阵写矩阵题最容易翻车的就是边界条件。我每次提交之前都会在心里默念几个极端输入空矩阵、单行、单列、1x1。如果矩阵只有一行比如 [[3, 1, 2]]那每一行的最小值就是整行最小值每一列的最大值就是那一列唯一的元素。这时候“行最小值”和“列最大值”的交集其实就是那个“在整行里最小、同时是所在列最大”的数。如果列数很多这个过程其实是在多个“列唯一值”里找一个同时满足“等于行最小值”的。用预处理法不需要特殊处理因为 rowMin 数组只有一个元素colMax 数组有 n 个元素正常算就行。如果矩阵只有一列比如 [[1], [2], [3]]那列最大值就是整列最大值行最小值就是每行的唯一元素。这时候幸运数如果存在一定是那个既是行最小值又是列最大值的元素。如果是 1x1 矩阵比如 [[7]]那 7 同时是行最小值和列最大值它天然就是幸运数。上面的所有代码都可以直接处理这种情况不会出错。4. 实战中的坑与排查记录4.1 误区一把“幸运数”理解成“全局最小/最大”不少人在读题时看到“行最小”和“列最大”脑子里会自动化简成“找一个又小又大的数”然后就开始往全局最小、全局最大方向想。这是一个很常见的误读。幸运数不是全局极值它只要求在自己的行和列里是极值跟矩阵里其他位置的大小没有直接关系。举个反例矩阵里有一个元素 5它是第 0 行的最小值也是第 2 列的最大值。但矩阵里还有比 5 更小的数比如 1跟这个结论不矛盾。所以你在写代码时一定不要先求全局 min 再求全局 max而是要老老实实地按“行”“列”两个维度分别处理。4.2 误区二忽略元素互不相同的限定前面反复强调“所有元素互不相同”这不是一个可有可无的细节而是决定幸运数唯一性的关键前提。一旦去掉这个前提一个矩阵里完全可能出现多个幸运数。我举一个极端例子1 1 1 1如果允许重复那四个 1 都是行最小值也都是列最大值幸运数就有四个。LeetCode 原题为了避免这种歧义直接声明了元素互不相同所以你可以放心地返回单个结果。但在扩展思考、或者面试官追问变体的时候你最好能说出“如果元素可重复解法需要怎么调整”这个点。4.3 误区三行列信息搞反我在写第二遍扫描列最大值时最容易犯的错误是循环变量的内外层顺序搞错。比如 c 代码里for (int i 0; i m; i) { for (int j 0; j n; j) { colMax[j] max(colMax[j], matrix[i][j]); } }有人会粗心写成矩阵按行遍历但更新的却一直是同一个 colMax 索引导致每列的统计结果完全错误。解决这个问题有一个小技巧先固定列号 j再遍历行号 i这样看代码的时候逻辑上更直观。不过更稳妥的做法是把统计列最大值单独写成一个双层循环内层遍历行外层遍历列不容易乱。for (int j 0; j n; j) { for (int i 0; i m; i) { colMax[j] max(colMax[j], matrix[i][j]); } }这种写法牺牲了一点点内存局部性但对初学者来说正确率更高。等你写熟练了再合并成单层循环也不迟。4.4 边界情况单行、单列、1x1之外的“空输入”除了矩阵形状的边界还要注意输入的矩阵本身可能为空比如matrix []。虽然 LeetCode 这道题的测试用例里可能没有这种输入但面试时你主动问一句“矩阵可能为空吗”会显得你考虑得比较周全。如果矩阵为空matrix[0]这行代码就会直接崩溃。所以我的习惯是函数开头先加一行if (matrix.empty() || matrix[0].empty()) return {};这样不管是空行还是空列都能安全返回空结果。5. 从1380发散出去一道简单题能带出多少东西5.1 面试热身题它到底在考什么很多人会觉得这种 Easy 题在面试里没有区分度其实不然。面试官出这道题考察的不是你会不会遍历矩阵而是三个更底层的点第一你能不能准确读懂“行最小”和“列最大”两个条件的组合含义。第二你愿不愿意多想一步挖掘出“幸运数最多只有一个”这个隐藏性质。第三你能不能写出一个结构清晰、边界安全、复杂度合理的解法。这三个点对应了从“能做出来”到“做好”的差距。如果你直接写暴力法面试官大概率会让你优化如果你能写出预处理法面试官会点头如果你还能顺手提出 max(行最小值) 和 min(列最大值) 相等的数学判断那这次面试基本就稳了。5.2 变式思考去掉“元素互不相同”会怎样这道题如果做变式最常见的就是去掉“元素互不相同”的限制。此时幸运数可能不唯一而且同一个数值可能在多个位置都满足条件。这时候有两种改法一种是把返回值改成所有满足条件的数值那就要在遍历时把所有同时命中行列条件的值都收集起来还要去重另一种是把返回值改成所有符合条件的坐标那就需要额外记录位置信息。你会发现去掉一个约束之后原来的“集合相交法”仍然可以工作因为行最小值集合和列最大值集合的交集就是所有可能的值只是在重复值较多时你需要进一步确认“这个值在对应的行里真的是最小值在对应的列里真的是最大值”。这时候反而回到了暴力判断的思路不过可以先通过集合筛选出少量候选再做精确验证性能依然很可观。5.3 简单题在刷题路线里的位置我刷 LeetCode 的时候会刻意把题目分成两类一类是“为了 AC 而刷”一类是“为了理解而刷”。像 1380 这种简单题明显属于后者。它不考你复杂的算法模板也不考你高深的数据结构但它能帮你强化一个意识任何题目在动手写代码之前都要先找一找它有没有数学性质或者隐含条件。这个意识在刷 LeetCode 热门 100 题、周赛 430 这类进阶内容时会特别管用。比如你在解旅行商这类状态压缩题时如果上来就套 DP 模板很容易把自己绕晕但如果你先想清楚“状态之间怎么转移、哪些状态可以被剪枝”思路就会清晰很多。简单题里练出来的“先分析性质再写代码”的习惯到最后反而比多刷十个模板题更有价值。5.4 所谓“热门100题”和难题的底层联系我现在回过头看这道题觉得它和解三角形面积、求岛屿最大面积这类矩阵题本质上共享一个底层技能对二维数组的遍历能力、对行列关系的理解能力、对预处理与查询分离的敏感度。你刷 LeetCode 时总结出来的不是一道题而是一类题的“解题手感”。比如热门 100 题里的“矩阵置零”就是先扫描一遍标记哪些行哪些列要置零再回头修改数组这就是预处理思想的直接应用再比如“搜索二维矩阵 II”你观察矩阵行列的排序规律从右上角开始走也是一种对行列关系的利用。1380 题虽然简单但它的核心思路和这些题目是同一个根源。所以我一直觉得刷题路线里不能只盯着难题和热门题。简单题如果能认真总结把背后的思维模型提炼出来再迁移到难题里效果往往比你直接啃一百道 hard 题要好得多。最后再分享一个小经验我每次刷完一道简单题都会强迫自己写一个“一句话总结”比如这道题就是“幸运数最多只有一个等于所有行最小值的最大值也等于所有列最大值的最小值”。这句话一出来整个题目的解法就牢牢刻在脑子里了。下次再遇到类似的题目你脑子里会直接跳出几个候选思路而不是从头开始琢磨。这种积累多了刷题速度自然会起来。 
长河君 · 2026/9/17 4:07:23 · 阅读 1.2k LeetCode矩阵幸运数：从暴力遍历到最优解的核心数学性质
LeetCode 1380题《Lucky Numbers in a Matrix矩阵中的幸运数》放在题库里就是一道不起眼的Easy题。但我在刷它的时候连续交了好几版执行用时一直徘徊在100ms上下排名惨不忍睹。后来回头一梳理才发现这道题根本不用那么绕它的核心其实是一个很漂亮的数学性质想明白了之后代码甚至可以压缩到几行。这篇文章就把我从“暴力遍历”到“最优解法”的完整思路、踩过的坑、以及从这道简单题里延伸出来的经验都整理出来分享给大家。这道题适合谁看如果你正在刷LeetCode、准备面试或者只是单纯想在矩阵题里找点手感这篇文章都可以给你一些参考。我会把每一种解法的推导过程、复杂度、以及为什么这么写都讲清楚。尤其是那个“幸运数最多只有一个”的隐藏性质很多讨论区里的高赞答案也是一句话带过但真正理解它之后你会发现整个题目瞬间从“查表题”变成了“数学题”。1. 题目到底在问什么幸运数的定义与直觉1.1 从题目描述说开去先看题目的原始定义给你一个 m x n 的矩阵如果一个元素 matrix[i][j] 同时满足两个条件那它就是幸运数它是第 i 行的最小值它是第 j 列的最大值。换句话说这个数在自己的行里“最小”在自己所在的列里“最大”。这听起来像什么就像一个人在班级里是某个科目倒数第一但在全校这个科目里又是正数第一听起来像是“错位”的评价体系里冒出来的一个奇怪交集。实际场景里这种数当然很少见所以题目才叫“幸运数”。我在读题的时候第一反应是这不就是双重条件判断吗每行找最小每列找最大然后看有没有重合的元素。思路本身不复杂但要注意一个容易被忽略的细节——题目明确说了矩阵里的所有元素是互不相同的distinct。这个条件非常关键它直接决定了解法的复杂度。1.2 一个容易忽略的隐含条件幸运数最多只有一个我第一次做这题的时候直接按照“可能不止一个幸运数”的思路去写用哈希表存了一堆候选值结果返回的时候还要考虑顺序把自己绕得不轻。后来重新读题才发现题目里已经埋好了线索所有元素不同而幸运数同时是“行最小”和“列最大”在互不相同的约束下幸运数最多只有一个。为什么这里可以给一个比较直观的证明思路。假设存在两个幸运数 x 和 y它们的位置分别在 (i1, j1) 和 (i2, j2)。因为 x 是第 i1 行的最小值而 y 也在这一行中的某个位置如果 i1 和 i2 相同那 x 和 y 在同一行两者又都是行最小值元素互不相同的话就矛盾了。同理因为 y 是第 j2 列的最大值那么 x 所在的第 i1 行、第 j2 列这个位置的值一定不比 y 大也不比 x 小最后会推出 x 和 y 必须相等。既然元素互不相同那 x 和 y 只能是同一个位置、同一个值。这个性质带来的最大简化就是最后返回的结果要么是空列表要么是只包含一个元素的列表。代码写起来可以放心大胆地直接 return 单个值不用考虑“多个幸运数按什么顺序返回”这种问题。2. 从暴力到优雅三种解法思路拆解2.1 第一反应暴力遍历逐个验证最容易想到的办法就是二重循环遍历每一个格子再花额外的时间去检查它是不是当前行的最小值、当前列的最大值。伪代码差不多是这样遍历矩阵中的每个元素 matrix[i][j]检查第 i 行里有没有比它更小的数检查第 j 列里有没有比它更大的数如果两个条件都满足直接返回。复杂度是多少矩阵是 m 行 n 列遍历每个格子是 O(mn)检查一次行要 O(n)检查一次列要 O(m)所以总时间复杂度是 O(mn*(mn))。如果题目给的矩阵是 50x50那也就是 5050100 250000 次操作现代机器跑起来秒钟级别完全没问题。但你要是在 LeetCode 上直接交这么一版大概率会发现自己排到了赛博朋克级别的“末端”。不是算法错了是这个思路太“厚道”了属于用计算量换思考量。如果矩阵规模变成 1000x1000暴力法的操作数就变成 10^9 级别普通的 OJ 环境可能直接给你一个超时。所以暴力法适合什么场景适合你在头脑发热、或者刚学完循环想练手的时候。真正刷题时一眼能看出暴力解但最好再逼自己想一想有没有空间换时间的做法2.2 角色互换先算行最小与列最大暴力法的问题在于每检查一个格子都要重复扫描整行整列。这个“重复扫描”完全没有必要。我们可以提前把所有行的最小值、所有列的最大值都算好之后再拿着这份“预计算表”去判断每个格子。具体的做法有两种变体我分别说一下。第一种是“数组存值法”开两个数组 rowMin[m] 和 colMax[n]第一遍遍历矩阵把 rowMin[i] 填成第 i 行的最小值第二遍遍历矩阵把 colMax[j] 填成第 j 列的最大值。第三遍遍历所有格子如果某个元素同时等于 rowMin[i] 和 colMax[j]那它就是幸运数。第二种是“集合相交法”把所有的行最小值塞进一个哈希集合 rowMinSet把所有的列最大值塞进另一个哈希集合 colMaxSet最后求这两个集合的交集。因为幸运数要同时满足“是行最小值”和“是列最大值”所以它必然同时出现在两个集合里交集里就是答案。这两种变体本质是一样的都是把“每次判断时重复扫描”变成“提前扫描一遍存起来”。时间复杂度从 O(mn(mn)) 降到了 O(m*n)内存开销 O(mn)。对于这道题来说这个复杂度已经非常够用了。2.3 更优雅的数学结论max(行最小值) 与 min(列最大值)如果你刷题刷得多了会慢慢养成一种直觉凡是“既是集合 A 又是集合 B”的题很多时候可以转化为“A 的某个极值和 B 的某个极值比较”。这道题就是典型。既然幸运数最多只有一个我其实不需要真的遍历所有格子去查交集只需要看两个数所有行最小值里的最大值记作 maxRowMin所有列最大值里的最小值记作 minColMax。如果 maxRowMin minColMax这个相等的值就是幸运数如果不相等矩阵里就没有幸运数。为什么这个结论成立我用自己的方式理解了一遍确实能讲通。假设存在某个幸运数 x它自己是某一行 i 的最小值那么 x 一定不小于这一行里的所有数所以 x 至少不会小于所有行最小值的最大值也就是说 x maxRowMin。另一方面 x 又是某一列 j 的最大值那么 x 一定不大于这一列里的所有数所以 x 不会大于所有列最大值的最小值也就是说 x minColMax。如果 x 真的存在那它必须同时满足这两个不等式那就必须有 maxRowMin x minColMax。同时因为 x 是行最小值之一所以 x maxRowMin又因为 x 是列最大值之一所以 x minColMax。把这两个方向一夹就能推出 x maxRowMin minColMax。反过来如果 maxRowMin minColMax那这个等号成立的位置就是那个同时满足两个条件的幸运数。这个结论的好处是你只需要扫描两遍矩阵分别求出 rowMin 数组和 colMax 数组然后再做一个求数组极值的操作就能得到答案连第三遍遍历矩阵都省了。代码可以写得非常干净也特别适合在面试时展示你对问题的理解深度。2.4 三种方案横向对比为了更直观地看出差别我整理了一张对比表。这里的时间和空间复杂度都是按 m 行 n 列来算的。解法时间复杂度空间复杂度代码量推荐程度暴力遍历O(mn(mn))O(1)少不推荐预处理行最小/列最大O(m*n)O(mn)中推荐max(行最小值) 与 min(列最大值)O(m*n)O(mn)少很推荐我个人在实际刷题时会选择第三种写法因为它把题目背后那个“最多只有一个幸运数”的性质用到了极致。但我也建议你至少把第二种写法练熟因为预处理思路在后续刷矩阵类题目时很常用比如旋转矩阵、蛇形遍历、岛屿问题都会用到“先扫一遍记录信息”的技巧。3. 代码实现与实测表现3.1 C实现一套顺手且不容易写错的写法我用 C 写的最顺手的版本是“预处理数组 双重遍历查值”逻辑清晰不容易写错。class Solution { public: vectorint luckyNumbers(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); vectorint rowMin(m, INT_MAX); vectorint colMax(n, INT_MIN); // 第一遍统计每一行的最小值 for (int i 0; i m; i) { for (int j 0; j n; j) { rowMin[i] min(rowMin[i], matrix[i][j]); } } // 第二遍统计每一列的最大值 for (int j 0; j n; j) { for (int i 0; i m; i) { colMax[j] max(colMax[j], matrix[i][j]); } } // 第三遍找到同时满足两个条件的元素 for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] rowMin[i] matrix[i][j] colMax[j]) { return {matrix[i][j]}; } } } return {}; } };这里要注意初始化的细节。rowMin 要初始化为 INT_MAX因为我们要不断取 min初始值必须是一个“大数”colMax 要初始化为 INT_MIN因为要不断取 max初始值必须是一个“小数”。很多初学者喜欢把 rowMin 初始化成 matrix[i][0]也不是不行但写成 INT_MAX / INT_MIN 可以避免处理空行空列的边界问题代码更稳。3.2 Python实现三行解决问题的技巧Python 写这种矩阵题最大的优势就是列表推导式。如果你用了“集合相交法”代码能精简到三种解法里最少的样子。class Solution: def luckyNumbers(self, matrix: List[List[int]]) - List[int]: row_mins {min(row) for row in matrix} col_maxs {max(col) for col in zip(*matrix)} return list(row_mins col_maxs)拆开解释一下。第一行min(row) for row in matrix得到每一行的最小值外面套一个集合推导式得到一个集合 row_mins。第二行zip(*matrix)的作用是“解压缩”矩阵的行把矩阵的列变成行相当于做了转置然后对每一列取 max得到每一列的最大值集合 col_maxs。第三行直接用集合的交集因为幸运数要同时满足两个条件所以正好是交集。这个版本为什么可以这么精简核心还是因为题目保证了元素互不相同所以 row_mins 和 col_maxs 的交集最多只有一个元素转换成 list 返回没有任何歧义。如果你面试时敢写出这种写法面试官多半会觉得你对 Python 的掌握很熟练。3.3 关于“耗时100”的一点实测感受题目标题里写的“耗时100”指的是我第一版暴力解法在 LeetCode 上提交后的执行用时恰好一百毫秒出头。放在很多年前的老评测机上这个成绩还能看但放到现在讨论区里一堆 0ms、4ms 的 C 解法我这个 100ms 就显得很扎眼。为什么暴力法会这么慢关键在于“重复扫描”。矩阵里每个格子都要做一次行内比较和列内比较而且这些比较完全没有利用已计算的信息。比如你检查完 (0, 0) 发现它是第 0 行的最小值等到检查 (0, 3) 的时候第 0 行的最小值你已经知道了但暴力法还是会重新把第 0 行扫一遍。这就是明显的重复劳动。优化之后用预处理法再提交执行用时基本能降到几毫秒到十几毫秒。这个差距恰恰说明了“先观察数据特点再决定算法”的重要性。其实 LeetCode 上显示的耗时本身会受到网络、服务器负载、测试用例波动的影响没必要特别迷信那几毫秒的差距但复杂度从 O(mn(mn)) 降到 O(m*n)这个优化是实打实的。3.4 边界条件单行、单列、1x1矩阵写矩阵题最容易翻车的就是边界条件。我每次提交之前都会在心里默念几个极端输入空矩阵、单行、单列、1x1。如果矩阵只有一行比如 [[3, 1, 2]]那每一行的最小值就是整行最小值每一列的最大值就是那一列唯一的元素。这时候“行最小值”和“列最大值”的交集其实就是那个“在整行里最小、同时是所在列最大”的数。如果列数很多这个过程其实是在多个“列唯一值”里找一个同时满足“等于行最小值”的。用预处理法不需要特殊处理因为 rowMin 数组只有一个元素colMax 数组有 n 个元素正常算就行。如果矩阵只有一列比如 [[1], [2], [3]]那列最大值就是整列最大值行最小值就是每行的唯一元素。这时候幸运数如果存在一定是那个既是行最小值又是列最大值的元素。如果是 1x1 矩阵比如 [[7]]那 7 同时是行最小值和列最大值它天然就是幸运数。上面的所有代码都可以直接处理这种情况不会出错。4. 实战中的坑与排查记录4.1 误区一把“幸运数”理解成“全局最小/最大”不少人在读题时看到“行最小”和“列最大”脑子里会自动化简成“找一个又小又大的数”然后就开始往全局最小、全局最大方向想。这是一个很常见的误读。幸运数不是全局极值它只要求在自己的行和列里是极值跟矩阵里其他位置的大小没有直接关系。举个反例矩阵里有一个元素 5它是第 0 行的最小值也是第 2 列的最大值。但矩阵里还有比 5 更小的数比如 1跟这个结论不矛盾。所以你在写代码时一定不要先求全局 min 再求全局 max而是要老老实实地按“行”“列”两个维度分别处理。4.2 误区二忽略元素互不相同的限定前面反复强调“所有元素互不相同”这不是一个可有可无的细节而是决定幸运数唯一性的关键前提。一旦去掉这个前提一个矩阵里完全可能出现多个幸运数。我举一个极端例子1 1 1 1如果允许重复那四个 1 都是行最小值也都是列最大值幸运数就有四个。LeetCode 原题为了避免这种歧义直接声明了元素互不相同所以你可以放心地返回单个结果。但在扩展思考、或者面试官追问变体的时候你最好能说出“如果元素可重复解法需要怎么调整”这个点。4.3 误区三行列信息搞反我在写第二遍扫描列最大值时最容易犯的错误是循环变量的内外层顺序搞错。比如 c 代码里for (int i 0; i m; i) { for (int j 0; j n; j) { colMax[j] max(colMax[j], matrix[i][j]); } }有人会粗心写成矩阵按行遍历但更新的却一直是同一个 colMax 索引导致每列的统计结果完全错误。解决这个问题有一个小技巧先固定列号 j再遍历行号 i这样看代码的时候逻辑上更直观。不过更稳妥的做法是把统计列最大值单独写成一个双层循环内层遍历行外层遍历列不容易乱。for (int j 0; j n; j) { for (int i 0; i m; i) { colMax[j] max(colMax[j], matrix[i][j]); } }这种写法牺牲了一点点内存局部性但对初学者来说正确率更高。等你写熟练了再合并成单层循环也不迟。4.4 边界情况单行、单列、1x1之外的“空输入”除了矩阵形状的边界还要注意输入的矩阵本身可能为空比如matrix []。虽然 LeetCode 这道题的测试用例里可能没有这种输入但面试时你主动问一句“矩阵可能为空吗”会显得你考虑得比较周全。如果矩阵为空matrix[0]这行代码就会直接崩溃。所以我的习惯是函数开头先加一行if (matrix.empty() || matrix[0].empty()) return {};这样不管是空行还是空列都能安全返回空结果。5. 从1380发散出去一道简单题能带出多少东西5.1 面试热身题它到底在考什么很多人会觉得这种 Easy 题在面试里没有区分度其实不然。面试官出这道题考察的不是你会不会遍历矩阵而是三个更底层的点第一你能不能准确读懂“行最小”和“列最大”两个条件的组合含义。第二你愿不愿意多想一步挖掘出“幸运数最多只有一个”这个隐藏性质。第三你能不能写出一个结构清晰、边界安全、复杂度合理的解法。这三个点对应了从“能做出来”到“做好”的差距。如果你直接写暴力法面试官大概率会让你优化如果你能写出预处理法面试官会点头如果你还能顺手提出 max(行最小值) 和 min(列最大值) 相等的数学判断那这次面试基本就稳了。5.2 变式思考去掉“元素互不相同”会怎样这道题如果做变式最常见的就是去掉“元素互不相同”的限制。此时幸运数可能不唯一而且同一个数值可能在多个位置都满足条件。这时候有两种改法一种是把返回值改成所有满足条件的数值那就要在遍历时把所有同时命中行列条件的值都收集起来还要去重另一种是把返回值改成所有符合条件的坐标那就需要额外记录位置信息。你会发现去掉一个约束之后原来的“集合相交法”仍然可以工作因为行最小值集合和列最大值集合的交集就是所有可能的值只是在重复值较多时你需要进一步确认“这个值在对应的行里真的是最小值在对应的列里真的是最大值”。这时候反而回到了暴力判断的思路不过可以先通过集合筛选出少量候选再做精确验证性能依然很可观。5.3 简单题在刷题路线里的位置我刷 LeetCode 的时候会刻意把题目分成两类一类是“为了 AC 而刷”一类是“为了理解而刷”。像 1380 这种简单题明显属于后者。它不考你复杂的算法模板也不考你高深的数据结构但它能帮你强化一个意识任何题目在动手写代码之前都要先找一找它有没有数学性质或者隐含条件。这个意识在刷 LeetCode 热门 100 题、周赛 430 这类进阶内容时会特别管用。比如你在解旅行商这类状态压缩题时如果上来就套 DP 模板很容易把自己绕晕但如果你先想清楚“状态之间怎么转移、哪些状态可以被剪枝”思路就会清晰很多。简单题里练出来的“先分析性质再写代码”的习惯到最后反而比多刷十个模板题更有价值。5.4 所谓“热门100题”和难题的底层联系我现在回过头看这道题觉得它和解三角形面积、求岛屿最大面积这类矩阵题本质上共享一个底层技能对二维数组的遍历能力、对行列关系的理解能力、对预处理与查询分离的敏感度。你刷 LeetCode 时总结出来的不是一道题而是一类题的“解题手感”。比如热门 100 题里的“矩阵置零”就是先扫描一遍标记哪些行哪些列要置零再回头修改数组这就是预处理思想的直接应用再比如“搜索二维矩阵 II”你观察矩阵行列的排序规律从右上角开始走也是一种对行列关系的利用。1380 题虽然简单但它的核心思路和这些题目是同一个根源。所以我一直觉得刷题路线里不能只盯着难题和热门题。简单题如果能认真总结把背后的思维模型提炼出来再迁移到难题里效果往往比你直接啃一百道 hard 题要好得多。最后再分享一个小经验我每次刷完一道简单题都会强迫自己写一个“一句话总结”比如这道题就是“幸运数最多只有一个等于所有行最小值的最大值也等于所有列最大值的最小值”。这句话一出来整个题目的解法就牢牢刻在脑子里了。下次再遇到类似的题目你脑子里会直接跳出几个候选思路而不是从头开始琢磨。这种积累多了刷题速度自然会起来。