给定一个初始元素全部为 0,大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示,其中的每个操作用一个含有两个正整数 a 和 b 的数组表示,含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后,你需要返回矩阵中含有最大整数的元素个数。
一开始不想进行过多思考,直接依照题目思路,3重FOR循环拉满,结果可想而知的运行超时了:
1 int maxCount(int m, int n, vector<vector<int>>& ops) { 2 3 // 二维数组初始化学习 4 vector<vector<int> > matrix(m, vector<int>(n, 0)); 5 6 int max = 0; //记录矩阵中的最大值 7 int total = 0; 8 9 for (auto i = ops.begin(); i != ops.end(); i++) { 10 int rows = i->at(0); 11 int cols = i->at(1); 12 13 for (int k = 0; k < rows; k++) 14 { 15 for (int s = 0; s < cols; s++) { 16 matrix[k][s] += 1; 17 18 max = max > matrix[k][s] ? max : matrix[k][s]; 19 } 20 } 21 } 22 23 for (int i = 0; i < m; i++) 24 { 25 for (int j = 0; j < n; j++) 26 { 27 if (matrix[i][j] == max) 28 { 29 total++; 30 } 31 } 32 } 33 34 35 return total; 36 }
思考之后发现每一个元素的 +1 操作其实都是从(0,0)开始操作的,那我只需要记录每一次进行过该操作的元素就行了,有点像层次叠加的模型过程,所以便有了如下代码,
(值得注意的是这里调整BUG我调整了很久,为了方便自己以后查看,特别红色注明:
我在取值过程中leetcode总是提示我代码问题,但是vs2017没有类似问题,即leetcode中无法取到ops[0][0]这样的数值,而vs2017则可以,后续可能值得注意。)
1 int maxCount2(int m, int n, vector<vector<int>>& ops) { 2 int total = 0; 3 4 int rowsOpeEle = m; 5 int colsOpeEle = n; 6 7 if(ops.empty()) 8 return m * n; 9 10 for (auto e : ops) { 11 int tmpRow = e[0]; 12 int tmpCol = e[1]; 13 14 if(tmpRow < rowsOpeEle) { 15 rowsOpeEle = tmpRow; 16 } 17 18 if(tmpCol < colsOpeEle) { 19 colsOpeEle = tmpCol; 20 } 21 22 total = rowsOpeEle * colsOpeEle; 23 } 24 25 return total; 26 }
再参考了一下题解答案,代码优雅度和简洁度方面还是存在差距,但是思考的方式还是没有问题:
int maxCount3(int m, int n, vector<vector<int>>& ops) { int mina = m,minb = n; for (const auto& op : ops) { mina = min(mina, op[0]); minb = min(minb, op[1]); } return mina * minb; }