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

解法一

因为矩阵是有序的，先对与第一行进行二分查找找到第一个负数的位置，根据位置计算本行的负数个数。后面行的第一个负数位置在第一行的基础上向前移动即可找到，然后也是根据位置计算当前行负数个数。
时间复杂度：，M为矩阵列的数量

class Solution {
    public int countNegatives(int[][] grid) {
        int pos = binarySearch(grid[0]);
        // 矩阵列数
        int m = grid[0].length;
        int ans = m - pos;
        for (int i = 1; i < grid.length; ++i) {
            if (grid[i][m - 1] >= 0) {
                continue;
            } else {
                pos = m - 1;
            }
            while ((pos > 0) && (grid[i][pos - 1] < 0)) {
                --pos;
            }
            ans += m - pos;
        }
        return ans;
    }
    private int binarySearch(int[] arr) {
        if (arr[arr.length - 1] >= 0) {
            return arr.length;
        }
        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (arr[mid] < 0) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}