diff options
author | Jack Sangdahl <[email protected]> | 2024-10-11 10:53:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-11 10:53:54 -0600 |
commit | 38020b428286de57d2ace617e4c5e8845bfa2be9 (patch) | |
tree | 92d747f16204ec789f98ca97a29981d779bb3024 /max_increase_city_skyline.c | |
parent | 0c21b6ec40d59bedd0dccb8b6049f3b3fe7f344a (diff) | |
download | leetcode-38020b428286de57d2ace617e4c5e8845bfa2be9.tar.gz leetcode-38020b428286de57d2ace617e4c5e8845bfa2be9.zip |
807. max increase to keep city skyline
Diffstat (limited to 'max_increase_city_skyline.c')
-rw-r--r-- | max_increase_city_skyline.c | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/max_increase_city_skyline.c b/max_increase_city_skyline.c new file mode 100644 index 0000000..3c9ab23 --- /dev/null +++ b/max_increase_city_skyline.c @@ -0,0 +1,56 @@ +// 807. Max Increase to Keep City Skyline +#include "leetcode.h" + +/* + * there is a city composed of 'n * n' blocks where each block contains a single + * building shaped like a vertical square prism. you are given 0 idxed 'n * n' + * integer matrix 'grid' where 'grid[r][c]' represents the height of the + * building located in the block at row 'r' and column 'c'. a city's skiline is + * the outer contour formed by all the building =hen viewing the side of the + * city from a distance. the skyline from a distance. the skyline from each + * cardinal direction, north, east, south, and west may be different. we are + * allowed to increase the height of any number of buildings by any amount. the + * height of a 0-height building can also be increased. however, increasing the + * height of a building should not affect the city's skyline from any cardinal + * direction. return the maximum total sum that the height of the buildings can + * be increased by without changing the city's skyline from any cardinal + * direction + */ + +int max_row(int **grid, int size, int idx) { + int max = INT_MIN; + for (int i = 0; i < size; i++) + if (grid[idx][i] > max) + max = grid[idx][i]; + return max; +} + +int max_col(int **grid, int size, int idx) { + int max = INT_MIN; + for (int i = 0; i < size; i++) + if (grid[i][idx] > max) + max = grid[i][idx]; + return max; +} + +int maxIncreaseKeepingSkyline(int **grid, int gridSize, int *gridColSize) { + int sum = 0; + int row_idx, col_idx, row_max, col_max; + for (row_idx = 0; row_idx < gridSize; row_idx++) + for (col_idx = 0; col_idx < gridColSize[row_idx]; col_idx++) { + row_max = max_row(grid, gridColSize[row_idx], row_idx); + col_max = max_col(grid, gridSize, col_idx); + sum += row_max > col_max ? col_max - grid[row_idx][col_idx] + : row_max - grid[row_idx][col_idx]; + } + return sum; +} + +int main() { + int g1[4][4] = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}}, + g2[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, gcs1 = 4, gcs2 = 3; + printf("%d\n", maxIncreaseKeepingSkyline((int **)g1, ARRAY_SIZE(g1), + &gcs1)); // expect: 35 + printf("%d\n", maxIncreaseKeepingSkyline((int **)g2, ARRAY_SIZE(g2), + &gcs2)); // expect: 0 +} |