题目描述
思路解析
一句话答案：LeetCode 1337 矩阵中战斗力最弱的 K 行：数出每行军人数，每行 1 都在前、有序可二分定界，再按军人数和行号排序取前 k 个行号，时间 O(m log n + m log m)。
军人多就强、军人少就弱，这题要返回哪几行
给一个只含 0 和 1 的矩阵，1 是军人、0 是平民，每行里军人都排在平民前头。一行军人越多战斗力越强，越少越弱；两行军人一样多时，行号小的那行算更弱。要返回战斗力最弱的 k 行行号，从最弱排到最强。题面例子 mat=[[1,1,0],[1,0,0],[1,1,1]]、k 取 2，三行军人数分别是 2、1、3，最弱两行是行 1、行 0，输出 [1, 0]。
每行从左数一遍 1，能过、可惜没吃到有序这张牌
每行从左往右一个个数 1，碰到第一个 0 就停，得到军人数；m 行数完再按军人数排序、取前 k 行——这样能过，只是每行数 1 是 O(n)。可题目给了一个条件：每行军人都在平民前面，这一行前半段全 1、后半段全 0，本身是有序的。找 1 和 0 的分界不必一格格挪，在有序的一行里二分——每次砍掉一半来定位分界，O(log n) 就够，行很长时省得明显。
数军人、按军人数和行号排序、取前 k 行
整道题拆成三步。一，数出每行军人数，也就是这行 1 的个数，用二分找 1 和 0 的分界即可。二，把每行看成「军人数、行号」这一对，按军人数从少到多排，军人数相同再按行号从小到大排。三，取最前面 k 个的行号，就是从最弱到最强的前 k 行。
平局靠行号分高下，稳定排序省一半事
军人数相同的两行怎么排，是这题唯一的岔子。规则是行号小的更弱、排前面，把「军人数、行号」一起当排序关键字，军人数打平时自动看行号就对了。还有个更省的写法：行号本来就是 0、1、2 递增排着的，用稳定排序——也就是关键字相等时保持原来先后次序的排法——只按军人数排，军人数一样的几行会保留原本的行号升序，同样满足规则。若排序不保证这点、又没显式比行号，平局两行就可能被打乱，输出就错。
三行例子、k 取 2，最弱两行怎么挑出来
先数军人。行 0 是 1、1、0，前两格是军人、第三格是平民，2 名；行 1 是 1、0、0，只有第一格是军人，1 名；行 2 是 1、1、1，全是军人，3 名。三行配上行号就是「2, 0」「1, 1」「3, 2」。
再排序。按军人数从少到多：1 名的行 1 最弱排第一，2 名的行 0 第二，3 名的行 2 最强排最后。k 是 2，取最前面两行的行号，答案 [1, 0]。换第一个例子 mat=[[1,0],[1,1]]、k 取 1 也走一遍：行 0 有 1 名、行 1 有 2 名，最弱是行 0，返回 [0]。
把军人数当答案返回、平局比反行号，都会让输出错位
这题栽跟头多在收尾。返回的是行号、不是军人数，写成返回军人数就答非所问；只取最弱的前 k 个，漏了截断会多吐几行。平局那下也别把行号比反，行号小的才更弱、排前面。全 0 或军人数全打平时，纯按行号从小到大即可。
复杂度上，数军人每行二分 O(log n)，m 行合起来 O(m log n)；给 m 行按「军人数、行号」排序 O(m log m)，整体 O(m log n + m log m)。Python 参考写法把每行逆序切片再 bisect，反转一行要 O(n)，数军人那部分退成 O(m·n)。空间存每行军人数和行号是 O(m)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这三步:数军人、按军人数和行号排序、取前 k 行。下面每一帧都在套这三步,先从数军人开始。
阶段一 · 逐行数军人：这就是 4 行 5 列的矩阵,绿色格子是军人也就是 1,蓝色格子是平民也就是 0。每行 1 都挤在左边。右边面板要记下每行的军人数,现在还空着。咱们一行一行来,从行 0 开始,从左往右数 1。
行 0 · 数到第 1 名军人：看行 0 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
行 0 · 数到第 2 名军人：看行 0 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
行 0 · 共 2 名军人：行 0 的第 2 格是 0,平民,数 1 到此为止。这行一共 2 名军人,记进右边面板。
行 1 · 数到第 1 名军人：看行 1 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
行 1 · 数到第 2 名军人：看行 1 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
行 1 · 数到第 3 名军人：看行 1 的第 2 格,是 1,一名军人,军人数加到 3。这一格是军人,继续往右看下一格。
行 1 · 数到第 4 名军人：看行 1 的第 3 格,是 1,一名军人,军人数加到 4。这一格是军人,继续往右看下一格。
行 1 · 共 4 名军人：行 1 的第 4 格是 0,平民,数 1 到此为止。这行一共 4 名军人,记进右边面板。
行 2 · 数到第 1 名军人：看行 2 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
行 2 · 共 1 名军人：行 2 的第 1 格是 0,平民,数 1 到此为止。这行一共 1 名军人,记进右边面板。
行 3 · 数到第 1 名军人：看行 3 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
行 3 · 数到第 2 名军人：看行 3 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
行 3 · 共 2 名军人：行 3 的第 2 格是 0,平民,数 1 到此为止。这行一共 2 名军人,记进右边面板。
阶段一完成 · 每行军人数已就位：四行都数完了。行 0 有 2 名,行 1 有 4 名,行 2 只有 1 名,行 3 有 2 名。军人数就是 2、4、1、2。注意行 0 和行 3 都是 2 名,打平了,这种平局等会儿要靠行号来分高下。下面进入排序。
阶段二 · 按军人数从少到多排序：现在每行军人数都有了。排序规则有两条:军人数少的更弱,排在前面;军人数一样时,行号小的更弱。咱们就照这个规则,从最弱的一行开始,一个一个往答案里挑。
挑出最弱 · 行 2：先找军人数最少的。行 2 只有 1 名军人,是全场最少,妥妥的最弱一行。把行 2 第一个放进答案,现在答案是 [2]。
平局 · 行 0 与行 3 都是 2 名：接着找次弱的。剩下行 0、行 1、行 3,军人数分别是 2、4、2。最少的是 2,但行 0 和行 3 都是 2 名,打平了。这时候看行号:行 0 的行号比行 3 小,所以行 0 更弱,该它先走。
挑出次弱 · 行 0：平局靠行号小的更弱,行 0 胜出,排在行 3 前面。把行 0 放进答案,现在答案是 [2, 0]。还差一行就凑齐 3 个了。
挑出第三弱 · 行 3：剩下行 1 和行 3,军人数 4 和 2。行 3 的 2 名更少,更弱,该它了。把行 3 放进答案,现在答案是 [2, 0, 3],正好凑满 3 行。剩下行 1 有 4 名军人,是最强的,排最后,用不上。
完整弱到强次序 · 2 → 0 → 3 → 1：把四行从弱到强排满就是行 2、行 0、行 3、行 1,对应军人数 1、2、2、4。其中行 0 和行 3 这对平局,靠行号让行 0 在前。k 是 3,只取最前面三行,后面的行 1 灰掉不要。
答案 · [2, 0, 3]：战斗力最弱的 3 行,从弱到强就是行 2、行 0、行 3,答案数组是 [2, 0, 3]。这就是整道题:数清每行军人,按军人数和行号排序,取最弱的前 k 行行号。
边界先想清:全 0 或全平局时纯按行号、平局永远行号小的更弱、只取最弱的前 k 个行号。
面试重点:每行有序所以能二分数军人、稳定排序让平局自动按行号、k 很小时用大小为 k 的堆把堆维护做到 O(m·log k)(总时间还要加数军人那部分:C++/Java O(m·log n)、Python O(m·n))。
参考代码
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 kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]: m, n = len(mat), len(mat[0]) ans = [n - bisect_right(row[::-1], 0) for row in mat] idx = list(range(m)) idx.sort(key=lambda i: ans[i]) return idx[:k]复杂度
- 时间：C++/Java O(m·log n + m·log m);Python O(m·n + m·log m)，m 是行数,n 是列数。数每行军人:C++/Java 用二分是 O(log n),m 行共 O(m·log n);Python 用逆序切片反转每行再 bisect,反转就是 O(n),m 行共 O(m·n)(和直接从左扫同阶,慢在反转那一抄)。给 m 行按(军人数,行号)排序三家都是 O(m·log m)。整体由这两部分相加,差别只在数军人那块
- 空间：O(m)(Python 反转额外 O(n))，存每行军人数和行号这一组数据是 O(m),答案数组 O(k)。Python 每行逆序切片会另抄一份长度 n 的临时行,峰值多占 O(n)。排序内部开销:C++ 与 Java 约 O(log m) 递归栈,Python 的 sort 最坏 O(m),按峰值整体记 O(m)
易错点
面试追问把动画讲成自己的话
追问数每行军人,为什么能用二分,比从左扫快在哪?
追问平局时为什么稳定排序能自动按行号升序,不用显式比行号?
追问如果 k 远小于行数,有没有更省的办法?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计有序矩阵中的负数
LeetCode 1351 · 简单 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题