|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importcom.fishercoder.common.utils.CommonUtils; |
| 4 | + |
| 5 | +/** |
| 6 | + * 807. Max Increase to Keep City Skyline |
| 7 | + * |
| 8 | + * In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. |
| 9 | + * We are allowed to increase the height of any number of buildings, |
| 10 | + * by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well. |
| 11 | + * At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, |
| 12 | + * must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles |
| 13 | + * formed by all the buildings when viewed from a distance. See the following example. |
| 14 | + * What is the maximum total sum that the height of the buildings can be increased? |
| 15 | + * |
| 16 | + * Example: |
| 17 | + * Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] |
| 18 | + * Output: 35 |
| 19 | + * Explanation: |
| 20 | + * The grid is: |
| 21 | + * [ [3, 0, 8, 4], |
| 22 | + * [2, 4, 5, 7], |
| 23 | + * [9, 2, 6, 3], |
| 24 | + * [0, 3, 1, 0] ] |
| 25 | + * |
| 26 | + * The skyline viewed from top or bottom is: [9, 4, 8, 7] |
| 27 | + * The skyline viewed from left or right is: [8, 7, 9, 3] |
| 28 | + * The grid after increasing the height of buildings without affecting skylines is: |
| 29 | + * gridNew = [ [8, 4, 8, 7], |
| 30 | + * [7, 4, 7, 7], |
| 31 | + * [9, 4, 8, 7], |
| 32 | + * [3, 3, 3, 3] ] |
| 33 | + * |
| 34 | + * Notes: |
| 35 | + * 1 < grid.length = grid[0].length <= 50. |
| 36 | + * All heights grid[i][j] are in the range [0, 100]. |
| 37 | + * 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. |
| 38 | + * */ |
| 39 | +publicclass_807 { |
| 40 | +publicstaticclassSolution1 { |
| 41 | +publicintmaxIncreaseKeepingSkyline(int[][]grid) { |
| 42 | +intsize =grid.length; |
| 43 | +int[]horizontalLimits =newint[size]; |
| 44 | +int[]verticalLimits =newint[size]; |
| 45 | +for (inti =0;i <size;i++) { |
| 46 | +inthorizontalLimit =grid[i][0]; |
| 47 | +for (intj =1;j <size;j++) { |
| 48 | +horizontalLimit =Math.max(horizontalLimit,grid[i][j]); |
| 49 | + } |
| 50 | +horizontalLimits[i] =horizontalLimit; |
| 51 | + } |
| 52 | +for (intj =0;j <size;j++) { |
| 53 | +intverticalLimit =grid[0][j]; |
| 54 | +for (inti =1;i <size;i++) { |
| 55 | +verticalLimit =Math.max(verticalLimit,grid[i][j]); |
| 56 | + } |
| 57 | +verticalLimits[j] =verticalLimit; |
| 58 | + } |
| 59 | +intincreases =0; |
| 60 | +for (inti =0;i <size;i++) { |
| 61 | +for (intj =0;j <size;j++) { |
| 62 | +if (grid[i][j] !=horizontalLimits[i] &&grid[i][j] !=verticalLimits[j]) { |
| 63 | +increases +=Math.min(horizontalLimits[i],verticalLimits[j]) -grid[i][j]; |
| 64 | + } |
| 65 | + } |
| 66 | + } |
| 67 | +returnincreases; |
| 68 | + } |
| 69 | + } |
| 70 | +} |