LeetCode-Go 题解：1337. The K Weakest Rows in a Matrix —— 利用“1 恒在 0 前“性质的按列扫描法

LeetCode-Go 题解：1337. The K Weakest Rows in a Matrix —— 利用"1 恒在 0 前"性质的按列扫描法

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

本篇围绕 LeetCode-Go 仓库中 1337.The-K-Weakest-Rows-in-a-Matrix 题解目录 的完整文档与源码，讲解"矩阵中最弱的 K 行"这一经典二维矩阵问题的两种解法：最直观的"计数 + 排序"思路，以及利用题目隐含有序性质、仓库实际采用的"按列扫描"高效解法。读完本文，你将掌握如何从题目条件中提取有序性、把"找最弱行"转化为"按列扫描 + 全 1 行补位"的 O(m·n) 级实现，并能独立阅读与运行该目录下的源码和测试。

题目解读：谁才是"最弱"的一行

题目给出一个m * n的矩阵mat，矩阵元素只有两类：1代表军人（soldiers），0代表平民（civilians）。需要返回矩阵中战斗力最弱的前 k 行的索引，且按从最弱到最强排序。

强弱比较规则（源自原文档）：

• 第i行的军人数量少于第j行，则第i行更弱；
• 若两行军人数量相同，则行号更小的行更弱；
• 军人总是站在一行的靠前位置，即每一行总是先出现若干个1，之后才是0。

也就是说，本题的"弱"是双重维度下的有序比较：先比军人个数（少者弱），再比行号（小者弱）。题目大意与原文一致：请你返回矩阵中战斗力最弱的k行的索引，按从最弱到最强排序。

输入输出示例与数据约束

示例 1（原文档 Example 1）：

输入：mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]] k = 3 输出：[2,0,3] 各行军人数量：row 0 -> 2，row 1 -> 4，row 2 -> 1，row 3 -> 2，row 4 -> 5 按从最弱到最强排序为 [2,0,3,1,4]

注意这里体现的比较细节：row 0 与 row 3 军人数量都为 2，因行号 0 < 3，所以 row 0 排在 row 3 之前。

示例 2（原文档 Example 2）：

输入：mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]] k = 2 输出：[0,2] 各行军人数量：row 0 -> 1，row 1 -> 4，row 2 -> 1，row 3 -> 1 按从最弱到最强排序为 [0,2,3,1]

约束条件（原文档 Constraints）：

规模很小（最大 100×100），因此最直观的暴力计数方案在复杂度上也完全可行；但本题真正的价值在于第二条解题思路利用了行内元素的有序性。

核心性质：军人总是排在一行的靠前位置

原文档特别强调了一个看似"多余"的条件："军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前"。

这个条件意味着每一行都可以写成如下形式：

1 1 ... 1 0 0 ... 0 ← k 个 1 → ← 剩余 0 →

即每一行的形态是1^k 0^(n-k)。由此可以推出两个有用的结论：

1. 某行的军人数量，等价于该行第一个出现0的列号（若整行全为1，则军人数量为n）；
2. 若按列优先（先遍历第 0 列、再第 1 列……）顺序扫描矩阵，那么越早遇到第一个0的行，军人数量越少——而按列扫描天然按行号从小到大访问，恰好同时满足了"军人数量少的排前面、数量相同时行号小的排前面"这两个比较规则。

解法二正是围绕这一性质设计的。

解法一：统计军人数量 + 排序（最直观的思路）

原文档首先给出了人人都能想到的思路：先统计每一行1的个数，再按"1 的个数升序、个数相同时按行号升序"排序，最后取前 k 个索引。

以下是按该思路写出的示意实现（仅供理解思路，非仓库原码；仓库最终采用的是解法二）：

package leetcode import "sort" func kWeakestRowsCounting(mat [][]int, k int) []int { type rowPower struct { cnt int // 该行军人（1）的数量 idx int // 原始行号 } rows := make([]rowPower, 0, len(mat)) for i := 0; i < len(mat); i++ { cnt := 0 for j := 0; j < len(mat[i]); j++ { if mat[i][j] == 1 { cnt++ } } rows = append(rows, rowPower{cnt: cnt, idx: i}) } // 军人数量升序；数量相同时行号升序 sort.Slice(rows, func(a, b int) bool { if rows[a].cnt != rows[b].cnt { return rows[a].cnt < rows[b].cnt } return rows[a].idx < rows[b].idx }) res := make([]int, k) for i := 0; i < k; i++ { res[i] = rows[i].idx } return res }

复杂度分析：统计每行军人数量需要遍历整个矩阵，为 O(m·n)；排序为 O(m·log m)；总时间复杂度 O(m·n + m·log m)，额外空间 O(m)。

可以继续优化的点：由于每行都是1^k 0^(n-k)的形态，求军人数量时其实不必线性扫描整行，可以在每行内做一次二分查找第一个0的位置，把单行计数降到 O(log n)，总复杂度变为 O(m·log n + m·log m)。不过题目规模很小，这种优化并非必须。

这种解法虽然正确，但它完全没有利用"1 恒在 0 前"这一条件，原文档也明确指出：解法二才是最优雅、最高效的解法。

解法二：按列扫描（仓库采用的高效解法）

思路推导

由于每一行都是1^k 0^(n-k)形态，最先出现0的行一定军人最少。于是可以逐列扫描：对第j列，从上到下检查每一行i，若mat[i][j] == 0且这一行在更左侧（第j-1列）还是1（或者j == 0），说明行i的第一个0恰好出现在第j列，此时就把行号i追加进结果。

因为外层按列j从小到大、内层按行i从小到大遍历，所以：

• 军人数量少的行（第一个0更靠左）先被追加；
• 军人数量相同的行，行号小的先被追加。

这两条恰好完整对应题目定义的强弱比较规则，连排序都不需要。最后再单独把"整行全为 1"的行按行号从小到大补到结果末尾即可。

仓库源码

仓库在 1337. The K Weakest Rows in a Matrix.go 中的实现与原文档给出的代码完全一致：

package leetcode func kWeakestRows(mat [][]int, k int) []int { res := []int{} for j := 0; j < len(mat[0]); j++ { for i := 0; i < len(mat); i++ { if mat[i][j] == 0 && ((j == 0) || (mat[i][j-1] != 0)) { res = append(res, i) } } } for i := 0; i < len(mat); i++ { if mat[i][len(mat[0])-1] == 1 { res = append(res, i) } } return res[:k] }

逐行拆解

1. 第一个双重循环：外层遍历列j（0到n-1），内层遍历行i（0到m-1）。判断条件mat[i][j] == 0 && ((j == 0) || (mat[i][j-1] != 0))的含义是：当前元素是0，且它的左侧元素是1（或它本身就是第 0 列）。这保证了每一行只在其"第一个 0"所在的列被追加一次，不会重复入队。
2. 第二个循环：遍历所有行，若最后一列（len(mat[0])-1）仍为1，说明该行全为1，即军人数量达到最大值n，应当排在所有出现0的行之后，因此按行号递增依次追加。
3. return res[:k]：由约束1 <= k <= m保证切片不会越界，直接截取前 k 个即为答案。

以示例 1 验证：第 0 列只有 row 2 是0，追加2；第 1 列 row 0、row 3 是第一个0，追加0、3；最终全 1 的 row 4 被补在末尾。得到res = [2,0,3,4]，取前 3 个即[2,0,3]，与预期输出一致。

复杂度分析：外层循环最多扫描 m·n 个元素，第二段循环扫描 m 行，最坏时间复杂度 O(m·n)；由于不需要额外的排序结构，除了结果切片本身，几乎无额外空间开销。相比解法一省去了排序，且常系数更小，从源码结构看是本题最优的实现方式。

两种解法对比

两种解法都满足题目的全部约束，解法二在实现简洁度与常数性能上更优，也是仓库 README 中明确推荐的"最优雅最高效的解法"。

仓库源码与测试验证

源码与测试文件结构

该题在仓库中与其他题目保持完全一致的目录组织方式，1337.The-K-Weakest-Rows-in-a-Matrix 目录 下包含三个文件：

• README.md：题目原文、大意、解题思路与代码；
• 1337. The K Weakest Rows in a Matrix.go：核心实现，即上文解法二；
• 1337. The K Weakest Rows in a Matrix_test.go：单元测试。

测试用例与运行方式

测试文件 1337. The K Weakest Rows in a Matrix_test.go 定义了Test_Problem1337，其中两个用例与原文档的 Example 1、Example 2 完全对应：

• mat = [[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]、k = 3，期望输出[2,0,3]；
• mat = [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]、k = 2，期望输出[0,2]。

测试框架使用 Go 标准库testing，并在用例中通过fmt.Printf打印输入与输出结果，便于肉眼比对。

在仓库根目录（Go 版本为 1.19，见 go.mod）下，可以单独运行该题测试：

go test "./leetcode/1337.The-K-Weakest-Rows-in-a-Matrix/" -run Test_Problem1337 -v

也可以按仓库提供的 gotest.sh 方式，对所有题解做整体覆盖率测试：

bash gotest.sh

gotest.sh 内部执行的是go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...，生成仓库根目录下的 coverage.txt 覆盖率文件，这体现了仓库"每题必带测试、用覆盖率约束代码质量"的组织约定。测试通过即证明解法二对两个官方示例均输出正确结果。

边界情况与易错点

• 全 1 行必须最后补位：若遗漏第二个循环，整行为1的行将永远不会被追加（因为扫描循环只处理出现0的行），导致结果缺少"最强"的行。这是本题最容易出错的地方。
• 防止同一行重复入队：扫描循环中(j == 0) || (mat[i][j-1] != 0)这个条件至关重要。去掉它，一行内后续的每个0都会把该行再次追加，破坏结果的长度与顺序。
• 切片越界：res[:k]依赖1 <= k <= m的约束保证安全；若去掉该约束，则需要先对res长度做防御性判断。
• 比较规则的双重性：按列扫描天然解决"军人数量相同按行号排序"的平局问题，这是该解法优于"只统计数量再直接排序"（不写稳定排序或自定义规则）的根因。

小结

1337. The K Weakest Rows in a Matrix 是一道典型的"条件即线索"题目：题目给出的"军人总是排在一行靠前位置"并非冗余信息，而是将矩阵每一行约束成1^k 0^(n-k)的有序结构，从而允许用按列扫描的方式，在无需排序的情况下同时满足"军人数量升序"与"行号升序"两个比较维度。LeetCode-Go 仓库以解法二作为该题的标准答案，并配套了与官方示例一一对应的单元测试。读者可以在此基础上，进一步把"二分查找每行第一个 0"与"按列扫描"两种思路结合，体会从题目条件中挖掘数据结构特性的通用方法论。

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