807. Max Increase to Keep City Skyline

算法 
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] ]

这个题目是说分别从上往下和从左往右看，取最大的高度为可视的高度，然后对其他地方高度进行填充，不破坏最大高度的情况下，求出能够增加的最大高度。
分别进行了两次遍历，用两个数组存储从上往下和从左往右的两组最大高度，然后遍历grid矩阵，用两组最大高度中的最小值来填充grid，求出增加的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[][]} grid
 * @return {number}
 */
    var maxIncreaseKeepingSkyline = function(grid) {
        var output=0;
        var top_bottom = [];
        var left_right = [];
 
        //从左往右
        for(let i=0;i<grid.length;i++){
            let max = 0;
            for (let j=0;j<grid.length;j++){ if(grid[i][j]>max){
                    max = grid[i][j];
                }
            }
            left_right[i] = max;
 
        }
 
        //从上往下
        for(let i=0;i<grid.length;i++){
            let max = 0;
            for (let j=0;j<grid.length;j++){ if(grid[j][i]>max){
                    max = grid[j][i];
                }
            }
            top_bottom[i] = max;
 
        }
 
        for(let i=0;i<grid.length;i++){
            for (let j=0;j<grid.length;j++){
                output += Math.min(top_bottom[i],left_right[j])-grid[i][j];
            }
 
        }
 
        return output;
    };

其实得到两个最大数组不用循环两次，放到一个双重循环就可以了。