LeetCode 1351. 统计有序矩阵中的负数
题目描述
题意分析
矩阵的每行从左到右、每列从上到下都按非递增顺序排列，统计严格小于零的元素个数。相同数值允许重复，零属于非负数，不能计入答案。
题目保证矩阵非空，行数与列数可以不同，不必是方阵。行内和列内分别有序，不代表按行拼成的一维序列也有序；进阶要求线性于行数与列数之和，不能逐个检查全部格子。
解法：从左下角阶梯扫描
核心思路
[!blue]
从左下角开始，让尚未处理的候选区域保持为第零行到
row、第col列到最后一列的矩形。这个角落兼具两个相反方向的大小信息：同行右侧不大于当前值，同列上方不小于当前值，因此一次比较就能排除整条边界。若当前值为负，同行右边所有值也都为负，当前行从
col到末尾的columns - col个格子可以一起计入，然后上移一行。此前被移除的更左列已经证明在候选行范围内全都非负，所以本行的负数不会遗漏在左边。若当前值非负，同列上面的所有值都不小于它，也都非负。可以把当前列从候选区域中整体排除，向右移一列，不增加计数。
每次负数分支计入一条尚未统计的行后缀并移除该行，非负分支只移除已证明无贡献的列。因此不会重复计算，也不会漏掉任何仍可能为负的位置。上移时无需把列指针重置，因为之前排除的列在更上方仍然非负。候选区域的行或列耗尽时即可结束。
解题步骤
- 将行指针放在最后一行，列指针放在第一列，答案初始化为零。
- 当前值小于零时，加入该行剩余列数
columns - col，再令row--。- 当前值大于等于零时，令
col++，排除这一列的剩余候选。- 重复直到行小于零或列达到列数，返回累计负数数量。
代码实现
class Solution {
public int countNegatives(int[][] grid) {
int row = grid.length - 1;
int col = 0;
int answer = 0;
int columns = grid[0].length;
while (row >= 0 && col < columns) {
if (grid[row][col] < 0) {
answer += columns - col;
row--;
} else {
col++;
}
}
return answer;
}
}
func countNegatives(grid [][]int) int {
row, col, answer := len(grid)-1, 0, 0
columns := len(grid[0])
for row >= 0 && col < columns {
if grid[row][col] < 0 {
answer += columns - col
row--
} else {
col++
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(m + n)$，行指针最多上移
m次，列指针最多右移n次，每步都减少一个维度。- 空间复杂度：$O(1)$，仅使用两个下标和计数变量，不修改原矩阵。
关键点总结
[!green]
- 左下角能根据正负一次排除一整行后缀或一整列，而非只处理一个格子。
- 负数整段计数后移除该行，非负数排除整列，两种操作都不重复计数。
- 已排除列在更上方仍非负，列指针始终不需要回退。
- 取严格小于零的判定，零和正数走同一个排除分支。
易错点总结
[!yellow]
- 把小于零写成小于等于零，会把零也算成负数。
- 遇负数只加一却直接上移，会漏掉同一行右侧已经确定的负数。
- 上移后把列指针重置到零，会重复检查已经排除的列，失去行列和级别的效率。
- 用行数计算本行剩余格子数，非方阵时会计错；这里必须使用列数。
- 把矩阵当成整体有序的一维数组二分，使用了题目没有保证的跨行顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 240. 搜索二维矩阵 II | 中等 | 复用从角落每次排除一行或一列的阶梯搜索；本题遇到负数可以整段累加。 |
| 74. 搜索二维矩阵 | 中等 | 对照排序条件：只有跨行也全局有序时，才可以把矩阵展平后二分。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！