题目重点：每行已按 0…01…1 排序，求整张矩阵最左侧含 1 的列；从逐行二分到 O(m+n) 阶梯扫描，并解释无 1 与列号口径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 返回整张矩阵中最小的列下标 c，使至少一行 matrix[r][c]=1；代码采用从 0 开始计数，全零或空矩阵返回 −1。若现场需要第几列的 1-based 编号，最后转换。
- 矩阵非空时为矩形；每行满足非递减的二值顺序 0…01…1。代码不逐项验证排序保证，因为验证本身需额外 O(mn) 扫描；输入若不满足承诺，结果不保证正确。
解题路线
- 朴素解逐格从左到右检查，首个含 1 的列即答案，O(mn)。逐行二分每行第一个 1，再取最小列，O(m log n)，符合题目的实现描述。
- 进一步利用所有行共享的‘最左候选列’：设 candidate=n。从第一行起，若 candidate 左侧一格为 1，就向左移动 candidate；在当前行碰到 0 时停止，转下一行。
- candidate 只会从 n 单调下降到 0，至多移动 n 次；每行最多有一次停止判断，所以总 O(m+n)。循环不变量是已处理行的最左 1 下标等于 candidate；如果还为 n，则已处理行都无 1。
- 若扫描后 candidate=n，说明所有行无 1，返回 −1；否则返回 candidate。即使某行全 1，指针也会走到 0，后续行不可能改进。
手动走一遍
[[0,0,1,1],[0,1,1,1],[0,0,0,1]]：第一行把 candidate 从 4 降到 2；第二行再降到 1；第三行在列 0 是 0，维持 1，所以最左包含 1 的列下标为 1。全零矩阵返回 −1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Find leftmost column containing 1 in row-wise 0...01...1 matrix."""
def first_one_column(matrix: list[list[int]]) -> int:
if not matrix or not matrix[0]:
return -1
cols = len(matrix[0])
if any(len(row) != cols for row in matrix):
raise ValueError("matrix must be rectangular")
candidate = cols
for row in matrix:
while candidate > 0 and row[candidate - 1] == 1:
candidate -= 1
return candidate if candidate < cols else -1
复杂度
m 行、n 列：阶梯扫描 O(m+n) 时间、O(1) 额外空间；逐行二分 O(m log n) 时间、O(1) 额外空间。若只有少量行而列极多，二分可能更快；选择取决于规模。
易错点与追问
容易失分的边界
- 把问题理解为每一行返回首个 1 的列表；题目是整张矩阵一个 first column。
- 每行二分后直接返回第一行结果，忘记后面行可能更靠左。
- 全零矩阵仍返回列 n 或 0，没给不存在的约定；空矩阵/空列需要单独处理。
- 利用单调指针却在每行重新设 candidate=n，退回 O(mn)。
继续深挖
- 若行顺序也是按每行 1 的数量排序，能否提早终止？需要怎样的额外保证？
- 若矩阵在磁盘上按行存储、一次读取成本高，逐行二分需要随机访问；顺序扫描与 I/O 模型要重新比较。
- 若每行 1 前可能有噪声 0，排序假设失效，需怎样验证或改成全扫描？
