807. Max Increase to Keep City Skyline

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

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation:
The grid is:
[ [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

• 1 < grid.length = grid[0].length <= 50.
• All heights grid[i][j] are in the range [0, 100].
• All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

---

題目翻譯:

在二維陣列網格中，每個值 grid [i][j]表示位於那裡的建築物的高度。我們被允許以任何數量增加任何數量的建築物的高度（不同建築物的數量可以不同）。高度 0 也被認為是建築物。

最後，當從網格的所有四個方向（即頂部，底部，左側和右側）觀察時，“天際線”必須與原始網格的天際線相同。城市的天際線是從遠處觀看時由所有建築物形成的矩形的外部輪廓。請參閱以下示例。

建築物高度可以增加的最大總和是多少？

程式思路:
簡單講就是掃橫的掃直的取最大數存成兩個陣列，之後兩陣列的最大數再取較小數的那個就是答案了。例如範例(0,0) 橫排最大值是 8 直排最大值是 9，所以能蓋的高度就是 min(8,9) = 8 了 後面以此類推。

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        vector <int> row_max_array;
        vector <int> col_max_array;
        for(auto i = 0;i < grid.size();i++)
        {
            int max = 0;
            for(auto j = 0; j< grid[0].size();j++)
            {
                if(i == 0) //Init
                {
                   col_max_array.emplace_back(grid[0][j]);
                }else
                {
                   if(grid[i][j] > col_max_array[j] )
                     col_max_array[j] = grid[i][j];
                }

                if(grid[i][j] > max )
                    max = grid[i][j];
            }
            row_max_array.emplace_back(max);
        }
        int result = 0;
        for(auto i = 0;i < grid.size();i++)
        {
            for(auto j = 0; j< grid[0].size();j++)
            {
                result += min(col_max_array[j],row_max_array[i]) - grid[i][j];
            }
        }
        return result;
    }
};