力扣链接：1351.统计有序矩阵中的负数

难度：⭐

✏️ 方法一：

解题关键词：二分查找

解题思路：在矩阵中，每个小数组应用二分查找，最后将总和加起来。

function countNegatives(grid: number[][]): number {
  const length = grid.length;
  let result = 0;

  for (let i = 0; i < length; i++) {
    const curCount = getArrNegativeNumsCount(grid[i]);
    result += curCount;
  }

  return result;
}

// 获取每个数组中负数的个数
const getArrNegativeNumsCount = (arr: number[]): number => {
  let left = 0;
  let right = arr.length - 1;
  let index = arr.length;

  while (left <= right) {
    const mid = Math.floor((right - left) / 2) + left;
    if (arr[mid] >= 0) {
      left = mid + 1;
    } else {
      index = mid;
      right = right - 1;
    }
  }

  return arr.slice(index).length;
};

✏️ 方法二：

解题关键词：指针

解题思路：因为该矩阵无论按照行还是按照列，都是以非严格递减顺序排列的，所以当我们第一个数组从后往前找到最后一个负数的位置 pos1 时，下一个数组中最后一个负数的 pos2 肯定在 [0, pos1] 中，利用这个特点，我们做循环

function countNegatives(grid: number[][]): number {
  const length = grid.length;
  const n = grid[0].length;
  let pos = n - 1;
  let result = 0;

  for (let i = 0; i < length; i++) {
    // 如果 pos 不在最后一个位置，说明该数组 pos 后面的都是负数，已经跳过了，这个时候要加上这个数字
    if (pos !== n - 1) {
      result += grid[i].slice(pos + 1).length || 0;
    }

    // 从后往前查找，找到最后一个负数的位置
    for (let j = pos; j >= 0; j--) {
      if (grid[i][j] < 0) {
        result++;
        pos = j;
      } else {
        break;
      }
    }
  }

  return result;
}