题目描述
思路解析
一句话答案：LeetCode 1380 矩阵中的幸运数：幸运数在它那行最小、同时在它那列最大。分别求出每行最小、每列最大两份集合，取交集就是答案，数字各不相同时至多一个，时间 O(m·n)。
要找的幸运数，到底长什么样
给一个 m 行 n 列、数字各不相同的矩阵 matrix。幸运数要同时满足两条：在它所在那一行里最小，在它所在那一列里又最大，缺一条都不算。要返回的是这些数本身，不是它们的行号列号，顺序随意。题面例子 matrix=[[3,7,8],[9,11,13],[15,16,17]] 的答案是 [15]，换成 [[7,8],[1,2]] 答案是 [7]。
照定义逐格验，慢在哪
一个数是不是幸运数，天然要看它那一行和那一列。照定义直接做，就对每个格子往它整行扫一遍确认最小、再往它整列扫一遍确认最大。矩阵有 m·n 个格子，每个都要花 m+n 的功夫核对，叠起来是 O(m·n·(m+n))，同一行、同一列被反复扫了很多遍，浪费全在这些重复上。
两份清单一取交，条件就凑齐了
这些重复是白费的：每行的最小、每列的最大各自只有一份，不必为每个格子重算。先扫一遍矩阵，把每行的最小值凑成集合 rows；再扫一遍，把每列的最大值凑成集合 cols。一个数在行里最小，它必然出现在 rows 里；在列里最大，必然出现在 cols 里。两个条件同时成立，等价于它同时落在两份集合中，也就是落在 rows 和 cols 的交集里。求出交集，就是全部幸运数。
三步走：行最小、列最大、求交集
落到三步。第一步逐行求最小，一行一行扫，每行记下最小的数丢进 rows。第二步逐列求最大，换成一列一列扫，每列记下最大的数丢进 cols。第三步求交集，既在 rows 又在 cols 里的数就是幸运数，收集返回。参考代码里 min(row) 求行最小、zip 星号 matrix 把矩阵转置后对每行 max 求出列最大，最后 rows & cols 求交集并返回列表。
拿题面的 3×3 矩阵，两趟扫下来看结果
逐行求最小：第 0 行 3、7、8 里最小是 3，第 1 行 9、11、13 里最小是 9，第 2 行 15、16、17 里最小是 15，rows={3,9,15}。逐列求最大：第 0 列 3、9、15 里最大是 15，第 1 列 7、11、16 里最大是 16，第 2 列 8、13、17 里最大是 17，cols={15,16,17}。求交集：3 和 9 都不在 cols，只有 15 两边都有——它在第 2 行里最小、又在第 0 列里最大，答案 [15]。
复杂度，还有两处一记反就全错
求每行最小、每列最大各把矩阵完整扫一遍，都是 O(m·n)，整体由扫矩阵主导，时间 O(m·n)；两份集合分别存 m 个和 n 个数，空间 O(m+n)。最坑的是把两条件记反——它要行里最小、列里最大，按行最大列最小去找，方向一反答案全错。另一种漏法是只验了行最小就下结论：题面里第 0 行最小 3、第 1 行最小 9 都是各自行里最小，可它俩所在列的最大都是 15，漏验列这一半，就会把 3 和 9 也误当幸运数。数字各不相同时幸运数至多一个，不必操心去重。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这三步:先求每行最小、再求每列最大、最后拿行最小去对它那一列的最大值,相等的就是幸运数。下面每一帧都在套这三步,先从逐行求最小开始。
阶段一 · 逐行求最小：这就是 3 行 4 列的矩阵,里面的数字各不相同。咱们先一行一行求最小值。右边面板记每行的最小值,现在还空着。从行 0 开始,从左往右扫,边走边记住目前见过的最小数。
行 0 · 看第 0 列(4)：行 0 从第一个数开始,第 0 列是 4,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
行 0 · 看第 1 列(7)：行 0 第 1 列是 7,比当前最小 4 大,最小值不变,还是 4。继续往右。
行 0 · 看第 2 列(14)：行 0 第 2 列是 14,比当前最小 4 大,最小值不变,还是 4。继续往右。
行 0 · 看第 3 列(9)：行 0 第 3 列是 9,比当前最小 4 大,最小值不变。这一行扫完了,最小值是 4,在第 0 列,记进右边面板。
行 1 · 看第 0 列(11)：行 1 从第一个数开始,第 0 列是 11,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
行 1 · 看第 1 列(10)：行 1 第 1 列是 10,比刚才的最小 11 还小,最小值换成 10,在第 1 列。继续往右。
行 1 · 看第 2 列(13)：行 1 第 2 列是 13,比当前最小 10 大,最小值不变,还是 10。继续往右。
行 1 · 看第 3 列(12)：行 1 第 3 列是 12,比当前最小 10 大,最小值不变。这一行扫完了,最小值是 10,在第 1 列,记进右边面板。
行 2 · 看第 0 列(3)：行 2 从第一个数开始,第 0 列是 3,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
行 2 · 看第 1 列(5)：行 2 第 1 列是 5,比当前最小 3 大,最小值不变,还是 3。继续往右。
行 2 · 看第 2 列(6)：行 2 第 2 列是 6,比当前最小 3 大,最小值不变,还是 3。继续往右。
行 2 · 看第 3 列(15)：行 2 第 3 列是 15,比当前最小 3 大,最小值不变。这一行扫完了,最小值是 3,在第 0 列,记进右边面板。
阶段二 · 逐列求最大：每行最小值都拿到了:行 0 是 4、行 1 是 10、行 2 是 3。现在换个方向,一列一列求最大值。从第 0 列开始,从上往下扫,边走边记住目前见过的最大数。
列 0 · 看第 0 行(4)：第 0 列从最上面开始,行 0 是 4,暂时把它当成这列的最大值。往下看有没有更大的。
列 0 · 看第 1 行(11)：第 0 列行 1 是 11,比刚才的最大还大,最大值换成 11,在第 1 行。继续往下。
列 0 · 看第 2 行(3)：第 0 列行 2 是 3,比当前最大 11 小,最大值不变。这一列扫完了,最大值是 11,记进右边面板。
列 1 · 看第 0 行(7)：第 1 列从最上面开始,行 0 是 7,暂时把它当成这列的最大值。往下看有没有更大的。
列 1 · 看第 1 行(10)：第 1 列行 1 是 10,比刚才的最大还大,最大值换成 10,在第 1 行。继续往下。
列 1 · 看第 2 行(5)：第 1 列行 2 是 5,比当前最大 10 小,最大值不变。这一列扫完了,最大值是 10,记进右边面板。
列 2 · 看第 0 行(14)：第 2 列从最上面开始,行 0 是 14,暂时把它当成这列的最大值。往下看有没有更大的。
列 2 · 看第 1 行(13)：第 2 列行 1 是 13,比当前最大 14 小,最大值不变,还是 14。继续往下。
列 2 · 看第 2 行(6)：第 2 列行 2 是 6,比当前最大 14 小,最大值不变。这一列扫完了,最大值是 14,记进右边面板。
列 3 · 看第 0 行(9)：第 3 列从最上面开始,行 0 是 9,暂时把它当成这列的最大值。往下看有没有更大的。
列 3 · 看第 1 行(12)：第 3 列行 1 是 12,比刚才的最大还大,最大值换成 12,在第 1 行。继续往下。
列 3 · 看第 2 行(15)：第 3 列行 2 是 15,最大值换成 15,在第 2 行。这一列扫完了,最大值是 15,记进右边面板。
阶段三 · 行最小是否等于该列最大：两份结果都齐了:每行最小是 4、10、3,每列最大是 11、10、14、15。最后一步,把每个行最小拿去对它那一列的最大值。如果某个行最小恰好就是它那一列的最大值,说明它行里最小、列里又最大,就是幸运数。咱们一个一个判。
判定行 0 的最小 4 · 淘汰：看行 0 的最小值 4,它在第 0 列。可这一列的最大值是 11,比 4 大,在第 1 行。4 在行里虽小,在列里却不是最大,差一口气,淘汰。
判定行 1 的最小 10 · 幸运数：看行 1 的最小值 10,它在第 1 列。这一列的最大值是 10,正好也是 10。行里它最小、列里它最大,两个条件同时满足,10 就是幸运数,亮起来。
判定行 2 的最小 3 · 淘汰：看行 2 的最小值 3,它在第 0 列。可这一列的最大值是 11,比 3 大,在第 1 行。3 在行里虽小,在列里却不是最大,差一口气,淘汰。
答案 · [10]：三个行最小都判完了:4 输给同列的 11,3 也输给同列的 11,只有 10 既是它那一行的最小,又是第 1 列的最大,稳稳当当当上幸运数。所以答案就是 [10]。整道题就是这三步:每行求最小、每列求最大、行最小对上该列最大就是幸运数。
边界想清:两条都要满足、单个元素自己就是幸运数、单行时行最小同时也是它那一列的最大。
面试重点:数字唯一时用反证法证明幸运数至多一个、分两趟可把空间压到 O(m)、Python 用 zip 星号转置来求每列最大。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def luckyNumbers(self, matrix: List[List[int]]) -> List[int]: rows = {min(row) for row in matrix} cols = {max(col) for col in zip(*matrix)} return list(rows & cols)复杂度
- 时间：O(m·n)，m 是行数,n 是列数。求每行最小要把整个矩阵扫一遍 O(m·n),求每列最大再扫一遍也是 O(m·n);对照判定时,数组写法两两比是 O(m·n),集合写法求交集是 O(m+n)。整体由扫矩阵主导,是 O(m·n)
- 空间：O(m + n)，存每行最小要 O(m),存每列最大要 O(n),按峰值是 O(m+n)。答案最多只有 min(m,n) 个数。集合写法峰值同样是 O(m+n),不随矩阵面积平方增长
易错点
面试追问把动画讲成自己的话
追问为什么数字各不相同时,幸运数最多只有一个?
追问能不能不开两个数组,空间压到更省?
追问Python 里 zip 星号 matrix 到底做了什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
矩阵对角线元素的和
LeetCode 1572 · 简单 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题