题目链接：https://leetcode.com/problems/max-increase-to-keep-city-skyline/

1、解题思路

2019年第一次刷题，找了中级里通过率最高的一道。这题较简单，我的代码通过了但比较笨，最后贴上leetcode网站里给出的解答，学习下。

2、我的代码

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int verticalNum = grid[0].length;
        int horizontalNum = grid.length;
        int[] verticalSkyline = new int[verticalNum];
        int[] horizontalSkyline = new int[horizontalNum];
        for (int i = 0; i < horizontalNum; i++) {
            int maxVertical = grid[i][0];
            for (int j = 0; j < verticalNum; j++) {
                if (grid[i][j] > maxVertical) {
                    maxVertical = grid[i][j];
                }
            }
            verticalSkyline[i] = maxVertical;
        }        
        for (int i = 0; i < verticalNum; i++) {
            int maxHorizontal = grid[0][i];
            for (int j = 0; j < horizontalNum; j++) {
                if (grid[j][i] > maxHorizontal) {
                    maxHorizontal = grid[j][i];
                }
            }
            horizontalSkyline[i] = maxHorizontal;
        }
        int increasedHeigth = 0;
        for (int i = 0; i < horizontalNum; i++) {
            for (int j = 0; j < verticalNum; j++) {
                int min = horizontalSkyline[i] < verticalSkyline[j] ? horizontalSkyline[i] : verticalSkyline[j];
                increasedHeigth += min - grid[i][j];
            }
        }
        return increasedHeigth;       
    }
}

3、网站上的解答

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int N = grid.length;
        int[] rowMaxes = new int[N];
        int[] colMaxes = new int[N];

        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
        }

        int ans = 0;
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];

        return ans;
    }
}