题目描述
思路解析动画文字版
记牢这三步:先求每行最小、再求每列最大、最后拿行最小去对它那一列的最大值,相等的就是幸运数。下面每一帧都在套这三步,先从逐行求最小开始。
阶段一 · 逐行求最小：这就是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题