807. Max Increase to Keep City Skyline

這題其實會發現 看四個方向是多餘的, 看其中兩個方向就可以 （其他兩個 skyline 會一樣

也就是看 rowMax, colMax 即可 , 然後每一點取 min(rowMax, colMax), 就是最後建築物的高度（不影響原本 skyline)

T: O(n^2)

S: O(n)

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        
        int[] rowMax = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
            }
        }
        int[] colMax = new int[n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += (rowMax[i] - grid[i][j]);
                grid[i][j] = rowMax[i];

            }
            //System.out.println(Arrays.toString(grid[i]));
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] >= colMax[j]) {
                    sum += (colMax[j] - grid[i][j]);
                    grid[i][j] = colMax[j];
                }                
            }
            //System.out.println(Arrays.toString(grid[i]));
        }
        
        return sum;
    }
}


/*
west north        east
8     9. 4 8 7.    8 
7                  7 
9                  9
3     9  4 8 7     3



can modify row max and col max

so replace row max first,
the replace col max, if grid value > col max, use min one
 
8487
7477
9487
3333



8
7
9
3
 
 original high
            [3,0,8,4],
            [2,4,5,7],
            [9,2,6,3],
            [0,3,1,0]

increasing height
5 4 0 3  = 12
5 0 2 0  = 7
0 2 2 4  = 8
3 0 2 3  = 8

16 +12+7 = 35 => this q ask for increasing height total


after height
            [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3]

*/

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        
        int[] rowMax = new int[n];
        int[] colMax = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                
                sum += (rowMax[i] - grid[i][j]); // 增高多少
                grid[i][j] = rowMax[i];
                
                if (grid[i][j] >= colMax[j]) { // 如果高度要降低
                    sum += (colMax[j] - grid[i][j]); // sum 要減掉降低的高度
                    grid[i][j] = colMax[j];
                }  
            }
        }
    
        return sum;
    }
}

其實只要取較小的那個來算就好 min(row max, col max), 就會是 grid[i][j] 上最後的高度

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        
        int[] rowMax = new int[n];
        int[] colMax = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }

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