1351. Count Negative Numbers in a Sorted Matrix

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix

簡單題目，有 Sorted 根本天使。續 88. 的概念，在 decreasing in row-wise and col-wise 的情況下，左上的數字是最大的，右下的數字是最小的。一開始我很關注這兩個最大最小值，一直在想能不能從這兩個點出發完成整個 Matrix 的計算，但這樣想就是會卡在說下一個 element 不知道要選左右的還是上下的，因為都比自己大（或自己小）。

後來轉念一想，其實從右上開始好像不錯！對於一個 col 來說他是最大值，對於 row 來說他是最小值。如果他小於 0，代表往下的 col element 都是小於 0。因此結構變為找尋一個 col 最大的負數，找到後更新 ans，接著往左位移（可以肯定這個值比剛剛的 pivot 來得大可能負可能正），做一樣的事情找到該 col 最大的負數值...依此類推時間複雜度為 O(n+m)。

class Solution {

public:

	int countNegatives(vector<vector<int>>& grid) {

			int m = grid.size();
			int n = grid[0].size();
			int cur_step = 0;
			int ans = 0;
			
			for (int i = n - 1; i >= 0; i--){
				for (int j = cur_step; j < m; j++) {
					if (grid[j][i] < 0) {
						ans += (m - j);
						break;
					}
					else {
						cur_step++;
					}
				}
				if(cur_step >= m) break;
			}

			return ans;
	}
};

Best Solution

TODO