Fork me on GitHub

Max Increase to Keep City Skyline

Posted on

Description

https://leetcode.com/problems/max-increase-to-keep-city-skyline/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        vector<int> rowArray(grid.size(), -1);
        vector<int> columnArray(grid[0].size(), -1);
        
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                rowArray[i] = max(rowArray[i], grid[i][j]);
                columnArray[j] = max(columnArray[j], grid[i][j]);
            }
        }
        
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                ret += (min(rowArray[i], columnArray[j]) - grid[i][j]);
            }
        }
        
        return ret;
    }
};