LeetCode 1380. Lucky Numbers in a Matrix 幸运数查找：LeetCode-Go 单次遍历解法详解-平芜编程栈

LeetCode 1380. Lucky Numbers in a Matrix 幸运数查找：LeetCode-Go 单次遍历解法详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 LeetCode 第 1380 题「矩阵中的幸运数」为对象，基于 LeetCode-Go 仓库的官方实现与配套单元测试，完整讲解幸运数的判定规则、单次遍历的优化思路、逐行代码剖析与正确性论证。读完本文，你将掌握如何在 O(m×n) 时间内仅用 O(n) 额外空间找出矩阵中的所有幸运数，并能复现仓库的测试与覆盖率验证流程。

题目定义与判定规则

原题（英文）定义如下：

Given am * nmatrix ofdistinctnumbers, return all lucky numbers in the matrix inanyorder. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

题目大意（原文中文版）：给你一个 m * n 的矩阵，矩阵中的数字各不相同。请你按任意顺序返回矩阵中的所有幸运数。幸运数是指矩阵中满足同时下列两个条件的元素：

在同一行的所有元素中最小（行内最小）
在同一列的所有元素中最大（列内最大）

判定规则需要抓住两个要点：

双重身份：一个元素必须同时具备「本行最小值」和「本列最大值」两个身份才算幸运数，只满足其一不成立；
互异前提：原题保证矩阵内所有元素互不相同，因此「最小/最大」的判定不会出现并列歧义；返回顺序任意（any order），即结果数组的排列顺序不影响判题正确性。

输入输出示例与约束

官方示例

Example 1

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

15 位于第 2 行（该行最小），同时是第 0 列的最大值（3、9、15 中最大），因此是唯一幸运数。

Example 2

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

12 是第 2 行的最小值，也是第 3 列（2、7、12）的最大值。

Example 3

Input: matrix = [[7,8],[1,2]] Output: [7]

7 是第 0 行的最小值，也是第 0 列（7、1）的最大值。

约束条件

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5
矩阵中所有元素互不相同

约束对算法设计有两个直接影响：

m、n 最大仅为 50，O(m×n) 甚至更宽松的算法都能通过评测，但仓库实现选择了理论最优的 O(m×n) 单次遍历；
元素值全部 ≥ 1，这使0可以安全地充当「未记录/未初始化」的哨兵值，是下文源码实现能成立的前提。

解题思路

方案一：朴素两遍扫描（可读性优先）

原文解题思路指出：这是简单题，按照题意遍历矩阵，找到同时满足 2 个条件的数输出即可。最直观的做法分两步：

第一遍扫描：分别统计每一行的最小值rowMin[i]与每一列的最大值colMax[j]；
第二遍扫描：遍历每个格子(i, j)，若matrix[i][j] == rowMin[i]且matrix[i][j] == colMax[j]，则该元素同时满足「行内最小 + 列内最大」，即为幸运数。

时间复杂度 O(m×n)，额外空间 O(m+n)（两个辅助数组）。

方案二：仓库实现的单次遍历（空间更省）

LeetCode-Go 的官方实现只做一遍扫描就把两件事同时完成：

一边求当前行的最小值m及其所在列号k；
一边滚动更新每列迄今的最大值t[j]；
若当前行最小值m恰好等于其所在列的迄今最大值t[k]，说明它暂时是「行内最小 + 列内最大」，先写入候选数组r[k]；
全部行处理完后，再做一次终验：候选值v仍等于t[k]，才确认它没有被后续行更大的列值「顶掉」。

相比朴素方案，额外空间从 O(m+n) 降为 O(n)（只与列数相关），并且在整个扫描过程中完成了大部分候选筛选，无需二次遍历矩阵。

源码逐行剖析

完整实现如下（与题目源码完全一致）：

func luckyNumbers(matrix [][]int) []int { t, r, res := make([]int, len(matrix[0])), make([]int, len(matrix[0])), []int{} for _, val := range matrix { m, k := val[0], 0 for j := 0; j < len(matrix[0]); j++ { if val[j] < m { m = val[j] k = j } if t[j] < val[j] { t[j] = val[j] } } if t[k] == m { r[k] = m } } for k, v := range r { if v > 0 && v == t[k] { res = append(res, v) } } return res }

第 1 步：三个数组的初始化

t, r, res := make([]int, len(matrix[0])), make([]int, len(matrix[0])), []int{}

t：记录每一列迄今为止的最大值，长度等于列数n，初值全部为 0；
r：记录候选幸运数（以下标为列号 k），长度同样为n，初值 0 兼任「未记录」哨兵；
res：最终结果切片。

因为所有元素值 ≥ 1，初值 0 不会与真实数据混淆，这是整个哨兵技巧成立的基础。

第 2 步：行遍历 + 列最大值滚动更新

for _, val := range matrix { m, k := val[0], 0 for j := 0; j < len(matrix[0]); j++ { if val[j] < m { m = val[j] k = j } if t[j] < val[j] { t[j] = val[j] } } ... }

内层循环同时干了两件事：

查找当前行最小值m及其列号k（对应第 8-10 行）；
滚动更新第j列的迄今最大值t[j]（对应第 12-14 行）。

由于t初值为 0 且矩阵元素 ≥ 1，第一行扫描时t[j] < val[j]恒成立，列最大值得以正确初始化。整个矩阵只需扫描一次，即可同时获得所有行的最小值信息和所有列的累计最大值信息。

第 3 步：候选记录

if t[k] == m { r[k] = m }

内层循环结束时，t[k]已经是「包含本行在内的第 k 列最大值」。此时若t[k] == m，说明m既是本行最小值，又是（迄今）本列最大值，先将其按列号写入候选数组r[k]。

注意这里只是暂记候选，因为后续行可能把第 k 列的最大值刷新得更大。

第 4 步：终验输出

for k, v := range r { if v > 0 && v == t[k] { res = append(res, v) } } return res

v > 0表示该位置确实记录过候选（0 是哨兵）；
v == t[k]验证候选在后续行中没有被超越，即它仍是最终列最大值；
双重检查都通过的值才是货真价实的幸运数。

为什么终验必不可少？

用一个反例说明。设矩阵为[[5,1],[6,7]]（元素互异，满足原题约束）：

第 0 行：最小值是 1（第 1 列），t = [5, 1]，t[1] == 1，于是r[1] = 1；
第 1 行：最小值是 6（第 0 列），同时第 1 列最大值被刷新为max(1, 7) = 7，t = [6, 7]，r[0] = 6；
终验：r[1] = 1但t[1] = 7，1 != 7，候选 1 被正确剔除；r[0] = 6且t[0] = 6，输出[6]。

验证结果：6 是第 1 行最小值（6 < 7），也是第 0 列最大值（max(5, 6) = 6），确实是幸运数；而 1 只是行内最小，并非列内最大，被终验拦截。若省略终验步骤，1 就会被错误输出。

正确性分析

一个值得记录的数学性质：互异矩阵中幸运数至多一个

原题保证元素互异，在此前提下可以严格证明幸运数至多只有一个。反证如下：

假设存在两个不同的幸运数 a 与 b，a 位于 (r1, c1)，b 位于 (r2, c2)。由于 a、b 分别是各自行的最小值、各自列的最大值，必然有 r1 ≠ r2 且 c1 ≠ c2（否则同一行出现两个最小值、或同一列出现两个最大值，与互异矛盾）。不妨设 a < b：

a 是 r1 行最小值 ⇒a < matrix[r1][c2]；
b 是 c2 列最大值 ⇒b > matrix[r1][c2]；
于是a < matrix[r1][c2] < b；
b 是 r2 行最小值 ⇒b < matrix[r2][c1]；
a 是 c1 列最大值 ⇒a > matrix[r2][c1]；
于是matrix[r2][c1] < a < b，与b < matrix[r2][c1]直接矛盾。

因此结论成立。推论：

返回值至多包含一个元素，这也解释了三个官方示例的输出均为单元素数组；
面试中可以先「找候选、判存在」，再决定是否返回，不必担心结果数组膨胀。

实现与性质的对应关系

仓库实现并不显式依赖互异性质：即使矩阵存在重复元素（如测试用例 3），候选记录 + 终验的逻辑依然能给出正确结果，鲁棒性比「两遍扫描严格判等」更宽松一些。

复杂度分析

时间复杂度：O(m×n)。两层循环恰好把矩阵每个元素访问一次，没有任何重复扫描；
空间复杂度：O(n)。t与r各为长度 n 的数组；在互异前提下结果res至多容纳 1 个元素；
与朴素两遍扫描对比：时间同为 O(m×n)；空间上，当列数 n 远小于行数 m 时，O(n) 相比 O(m+n) 优势明显。

边界情况

1×1 矩阵：唯一元素既是行内最小又是列内最大，天然是幸运数；
单行矩阵（1×n）：每列只有一个元素，恒为该列最大值，因此幸运数唯一，即整行的最小值；
单列矩阵（m×1）：每行只有一个元素，恒为该行最小值，因此幸运数唯一，即整列的最大值；
最值出现在边角：判定只依赖行、列内的相对大小，与元素位置无关，逻辑不受影响；
元素重复（放宽约束）：如测试用例[[1,2,3,4,5],[1,2,3,4,5]]，实现仍能输出[1]（1 同时是两行的最小值与第 0 列的最大值）。

测试验证与覆盖率

仓库为本题配备了独立的单元测试 1380. Lucky Numbers in a Matrix_test.go，采用结构体驱动的表格测试风格（question1380组合para1380与ans1380），共 4 个用例：

输入矩阵	期望输出	用例来源
`[[3,7,8],[9,11,13],[15,16,17]]`	`[15]`	README 示例 1
`[[1,10,4,2],[9,3,8,7],[15,16,17,12]]`	`[12]`	README 示例 2
`[[1,2,3,4,5],[1,2,3,4,5]]`	`[1]`	附加用例（放宽互异约束）
`[[7,8],[1,2]]`	`[7]`	README 示例 3

其中用例 3 值得注意：它并不满足原题「元素互不相同」的约束，属于对实现的额外压力测试，验证了算法不依赖互异性质。

在仓库根目录执行以下命令即可运行本题测试：

go test -v ./leetcode/1380.Lucky-Numbers-in-a-Matrix/

覆盖率方面，仓库根目录的 coverage.txt 中记录了本题函数的全部执行块（覆盖计数均为正），说明测试完整执行了幸运数函数的每一行逻辑。全仓库覆盖率由 gotest.sh 统一生成，核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

模块信息见 go.mod：module github.com/halfrost/LeetCode-Go，Go 版本 1.19。此外，仓库主 README 声明全部题解遵循 Google Golang Style Guide 代码风格，本题实现同样是这一风格约束下的产物。

小结

幸运数的本质：一个元素 = 行内最小 ∩ 列内最大，两个条件缺一不可；
核心解法：LeetCode-Go 用单次遍历 + 两个长度为 n 的数组完成判定，时间复杂度 O(m×n)、额外空间 O(n)；
终验步骤：候选记录后必须复核v == t[k]，防止候选被后续行更大的列值「顶掉」；
互异性质：互异矩阵中幸运数至多一个，可用于快速判空与面试推导加分。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考