矩阵中的幸运数 图解题解
这道题到底在问什么
- 输入
- matrix=[[3,7,8],[9,11,13],[15,16,17]]
- 输出
- [15]
- 输入
- matrix=[[7,8],[1,2]]
- 输出
- [7]
先想最直接的笨办法
两份结果都齐了:每行最小是 4、10、3,每列最大是 11、10、14、15。最后一步,把每个行最小拿去对它那一列的最大值。如果某个行最小恰好就是它那一列的最大值,说明它行里最小、列里又最大,就是幸运数。咱们一个一个判。（动画第 30 步）
最优解：一步一步想明白
- 3记牢这三步:先求每行最小、再求每列最大、最后拿行最小去对它那一列的最大值,相等的就是幸运数。下面每一帧都在套这三步,先从逐行求最小开始。
- 4橙格 = 当前看的数,浅橙 = 这行暂时的最小这就是 3 行 4 列的矩阵,里面的数字各不相同。咱们先一行一行求最小值。右边面板记每行的最小值,现在还空着。从行 0 开始,从左往右扫,边走边记住目前见过的最小数。
- 5橙 = 当前,浅橙 = 暂时最小行 0 从第一个数开始,第 0 列是 4,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
- 6橙 = 当前,浅橙 = 暂时最小行 0 第 1 列是 7,比当前最小 4 大,最小值不变,还是 4。继续往右。
- 7橙 = 当前,浅橙 = 暂时最小行 0 第 2 列是 14,比当前最小 4 大,最小值不变,还是 4。继续往右。
- 8扫到第 3 列(9),本行最小 = 4行 0 第 3 列是 9,比当前最小 4 大,最小值不变。这一行扫完了,最小值是 4,在第 0 列,记进右边面板。
- 9橙 = 当前,浅橙 = 暂时最小行 1 从第一个数开始,第 0 列是 11,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
- 10橙 = 当前,浅橙 = 暂时最小行 1 第 1 列是 10,比刚才的最小 11 还小,最小值换成 10,在第 1 列。继续往右。
- 11橙 = 当前,浅橙 = 暂时最小行 1 第 2 列是 13,比当前最小 10 大,最小值不变,还是 10。继续往右。
- 12扫到第 3 列(12),本行最小 = 10行 1 第 3 列是 12,比当前最小 10 大,最小值不变。这一行扫完了,最小值是 10,在第 1 列,记进右边面板。
- 13橙 = 当前,浅橙 = 暂时最小行 2 从第一个数开始,第 0 列是 3,暂时把它当成这行的最小值。接着往右看,看有没有更小的。
- 14橙 = 当前,浅橙 = 暂时最小行 2 第 1 列是 5,比当前最小 3 大,最小值不变,还是 3。继续往右。
- 15橙 = 当前,浅橙 = 暂时最小行 2 第 2 列是 6,比当前最小 3 大,最小值不变,还是 3。继续往右。
- 16扫到第 3 列(15),本行最小 = 3行 2 第 3 列是 15,比当前最小 3 大,最小值不变。这一行扫完了,最小值是 3,在第 0 列,记进右边面板。
- 17橙格 = 当前看的数,浅橙 = 这列暂时的最大每行最小值都拿到了:行 0 是 4、行 1 是 10、行 2 是 3。现在换个方向,一列一列求最大值。从第 0 列开始,从上往下扫,边走边记住目前见过的最大数。
- 18橙 = 当前,浅橙 = 暂时最大第 0 列从最上面开始,行 0 是 4,暂时把它当成这列的最大值。往下看有没有更大的。
- 19橙 = 当前,浅橙 = 暂时最大第 0 列行 1 是 11,比刚才的最大还大,最大值换成 11,在第 1 行。继续往下。
- 20扫到第 2 行(3),本列最大 = 11第 0 列行 2 是 3,比当前最大 11 小,最大值不变。这一列扫完了,最大值是 11,记进右边面板。
- 21橙 = 当前,浅橙 = 暂时最大第 1 列从最上面开始,行 0 是 7,暂时把它当成这列的最大值。往下看有没有更大的。
- 22橙 = 当前,浅橙 = 暂时最大第 1 列行 1 是 10,比刚才的最大还大,最大值换成 10,在第 1 行。继续往下。
- 23扫到第 2 行(5),本列最大 = 10第 1 列行 2 是 5,比当前最大 10 小,最大值不变。这一列扫完了,最大值是 10,记进右边面板。
- 24橙 = 当前,浅橙 = 暂时最大第 2 列从最上面开始,行 0 是 14,暂时把它当成这列的最大值。往下看有没有更大的。
- 25橙 = 当前,浅橙 = 暂时最大第 2 列行 1 是 13,比当前最大 14 小,最大值不变,还是 14。继续往下。
- 26扫到第 2 行(6),本列最大 = 14第 2 列行 2 是 6,比当前最大 14 小,最大值不变。这一列扫完了,最大值是 14,记进右边面板。
- 27橙 = 当前,浅橙 = 暂时最大第 3 列从最上面开始,行 0 是 9,暂时把它当成这列的最大值。往下看有没有更大的。
- 28橙 = 当前,浅橙 = 暂时最大第 3 列行 1 是 12,比刚才的最大还大,最大值换成 12,在第 1 行。继续往下。
- 29扫到第 2 行(15),本列最大 = 15第 3 列行 2 是 15,最大值换成 15,在第 2 行。这一列扫完了,最大值是 15,记进右边面板。
- 30橙 = 待判定的行最小,浅橙 = 它那一列的最大两份结果都齐了:每行最小是 4、10、3,每列最大是 11、10、14、15。最后一步,把每个行最小拿去对它那一列的最大值。如果某个行最小恰好就是它那一列的最大值,说明它行里最小、列里又最大,就是幸运数。咱们一个一个判。
- 31列 0 的最大是 11,更大看行 0 的最小值 4,它在第 0 列。可这一列的最大值是 11,比 4 大,在第 1 行。4 在行里虽小,在列里却不是最大,差一口气,淘汰。
- 3210 同时是列 1 的最大看行 1 的最小值 10,它在第 1 列。这一列的最大值是 10,正好也是 10。行里它最小、列里它最大,两个条件同时满足,10 就是幸运数,亮起来。
- 33列 0 的最大是 11,更大看行 2 的最小值 3,它在第 0 列。可这一列的最大值是 11,比 3 大,在第 1 行。3 在行里虽小,在列里却不是最大,差一口气,淘汰。
- 34幸运数:10三个行最小都判完了:4 输给同列的 11,3 也输给同列的 11,只有 10 既是它那一行的最小,又是第 1 列的最大,稳稳当当当上幸运数。所以答案就是 [10]。整道题就是这三步:每行求最小、每列求最大、行最小对上该列最大就是幸运数。
⚠️ 容易写错的地方
✗ 错：把两个条件记反:以为是行最大、列最小
✓ 对：幸运数是行里最小、同时列里最大
方向记反就会找错格子,务必记牢「行最小、列最大」这一对搭配
✗ 错：只验了行最小,忘了再验列最大
✓ 对：两个条件要同时成立,缺一不可
本例里 4 和 3 都是各自行的最小,但同列有更大的 11,只验一半就会把它们误判成幸运数
✗ 错：担心会有很多个幸运数要去重
✓ 对：矩阵里幸运数最多只有一个
数字各不相同时,行最小且列最大的格子至多一个,不必担心重复,但代码仍按返回列表来写
✗ 错：返回成行号列号或最大最小的统计值
✓ 对：返回的是幸运数本身的数值列表
题目要的是那些数,不是它们的位置,也不是每行最小或每列最大的清单
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> luckyNumbers(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int rows[m];
int cols[n];
memset(rows, 0x3f, sizeof(rows));
memset(cols, 0, sizeof(cols));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
rows[i] = min(rows[i], matrix[i][j]);
cols[j] = max(cols[j], matrix[i][j]);
}
}
vector<int> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rows[i] == cols[j]) {
ans.push_back(rows[i]);
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public List<Integer> luckyNumbers(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] rows = new int[m];
int[] cols = new int[n];
Arrays.fill(rows, 1 << 30);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
rows[i] = Math.min(rows[i], matrix[i][j]);
cols[j] = Math.max(cols[j], matrix[i][j]);
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rows[i] == cols[j]) {
ans.add(rows[i]);
}
}
}
return ans;
}
}复杂度
时间
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 / Java / C++ 跟着练。
面试官可能追问
为什么数字各不相同时,幸运数最多只有一个?+
可以用反证法。假设有两个幸运数 a 和 b,分别在不同的行和不同的列。看 a 所在行、b 所在列交叉的那个格子 c。因为 a 是它那一行的最小,所以 a 小于等于 c;因为 b 是它那一列的最大,所以 c 小于等于 b。连起来就得到 a 小于等于 b。同样的道理,从 b 所在行、a 所在列又能推出 b 小于等于 a。两个一起,只能 a 等于 b。可数字各不相同,不允许相等,矛盾。所以幸运数最多一个。
能不能不开两个数组,空间压到更省?+
可以分两趟做。第一趟只算每行最小,顺手把这些候选记下来,它们最多 m 个。第二趟针对每个候选,单独去它那一列扫一遍,看它是不是这一列的最大。这样只额外存了候选,空间能压到 O(m)。但代价是逐个候选扫列,验证这步是 O(m^2),当列数 n 比行数小的时候总时间可能比开两个数组更慢,本质是拿时间换空间,实战里直接开两个数组更直白。
Python 里 zip 星号 matrix 到底做了什么?+
星号把 matrix 这个二维列表拆成一行一行的参数传给 zip,zip 再把它们按列对齐打包。结果就是原矩阵的转置,原来的第 j 列变成了新的第 j 行。这样对转置后的每一行求 max,得到的正是原矩阵每一列的最大值。它是 Python 求列方向统计的一个很顺手的写法。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 矩阵中的幸运数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。