807 Max Increase to Keep City Skyline

807. Max Increase to Keep City Skyline

1.Question

In a 2 dimensional arraygrid, each valuegrid[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 heightsgrid[i][j]are in the range[0, 100].

• All buildings ingrid[i][j]occupy the entire grid cell: that is, they are a1 x 1 x grid[i][j]rectangular prism.

2. Implementation

思路:

用rowMax[]存储每一行最大的值，colMax[]存储每一列最大的值，然后第一次遍历grid时填充这两个数组。第二次遍历grid，如果当前的高度grid[i][j] 比 rowMax[i]和colMax[j]都小的话，res加上rowMax[i]和colMax[j]两者中较小值与grid[i][j]的差

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] rowMax = new int[m];
        int[] colMax = new int[n];

        for (int i = 0; i < m; i++) {
            int curRowMax = 0;
            for (int j = 0; j < n; j++) {
                curRowMax = Math.max(curRowMax, grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
            rowMax[i] = curRowMax;
        }

        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int curMaxHeight = Math.min(rowMax[i], colMax[j]);
                if (grid[i][j] < curMaxHeight) {
                    res += curMaxHeight - grid[i][j];
                }
            }
        }
        return res;
    }
}

3.Time & Space Complexity

时间复杂度O(mn), 空间复杂度O(m + n)