1351.统计有序矩阵中的负数

/*
 * @lc app=leetcode.cn id=1351 lang=typescript
 *
 * [1351] 统计有序矩阵中的负数
 */

// @lc code=start
/* 原始写法：线性扫描 O(m * n) */
// function countNegatives(grid: number[][]): number {
// 	let result = 0;
// 	grid.map(item => {
// 		let l = 0,
// 			r = item.length - 1;
// 		if (item[r] >= 0) return; // 此行不存在负数
// 		while (l <= r) {
// 			if (item[l] < 0) {
// 				result += r - l + 1;
// 				break;
// 			}
// 			l++;
// 		}
// 	});
// 	return result;
// }

// 优化写法：阶梯法 O(m + n)，利用行列都非递增的特性
function countNegatives(grid: number[][]): number {
	const m = grid.length;
	const n = grid[0].length;
	let result = 0;
	let row = 0;
	let col = n - 1;

	while (row < m && col >= 0) {
		if (grid[row][col] < 0) {
			// 当前位置是负数，这一列从 row 到 m-1 都是负数
			result += m - row;
			col--;
		} else {
			// 当前位置非负，往下一行找
			row++;
		}
	}
	return result;
}

// test
let grid = [
	[4, 3, 2, -1],
	[3, 2, 1, -1],
	[1, 1, -1, -2],
	[-1, -1, -2, -3],
];

console.log(countNegatives(grid));

// @lc code=end