题目描述
思路解析动画文字版
记牢这三步:数军人、按军人数和行号排序、取前 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题