Max Increase to Keep City Skyline
给一个2d数组, 求不改变里面数字对应行列最大值的情况下, 数组数字最大增加多少.
这题读懂题很关键, 先找行列对应的最大值, 然后再用两个值中小的那个减去现有的值, res += min(row[i], col[j]) – grid[i][j], where row[i], col[j] is the max number of i, j.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); vector<int> col(m); vector<int> row(n); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { row[i] = max(row[i], grid[i][j]); col[j] = max(col[j], grid[i][j]); } } int res = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { res += min(row[i], col[j]) - grid[i][j]; } } return res; } }; |