807. Maintain the urban skyline

Address ： 

Power button https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

subject ：

Give you a seat by n x n A city of blocks , Each block contains a cube building . I'll give you a subscript from 0 At the beginning n x n Integer matrix grid , among grid[r][c] Located in r That's ok c Of a row of buildings Height .

The city's The skyline When you look at the city from a distance , The external contour formed by all buildings . From the East 、 south 、 In the west 、 Observed in the four main directions of the North The skyline It may be different .

We are allowed to Any number of buildings Increase the height of Any increment （ The increment of different buildings may be different ） . The height is 0 The height of buildings can also be increased . However , Increased building height Can not affect Looking at the city from any major direction The skyline .

stay Don't change Cities observed from any major direction The skyline Under the premise of , Return to the building can add The sum of the maximum height increments .

Example 1：

Input ：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] Output ：35 explain ： The height of the building is shown in the center of the figure above . Draw the skyline in red from different directions . Without affecting the skyline , Increase the height of the building ： gridNew = [ [8, 4, 8, 7],             [7, 4, 7, 7],             [9, 4, 8, 7],             [3, 3, 3, 3] ]

Example 2：

Input ：grid = [[0,0,0],[0,0,0],[0,0,0]] Output ：0 explain ： Increasing the height of any building will change the skyline .

 

Tips ：

n == grid.length n == grid[r].length 2 <= n <= 50 0 <= grid[r][c] <= 100

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

The title is more abstract , It took a little time to understand the picture ; Take a little more time to understand what to do

As shown in the figure , Explain the relationship between matrix and graph in one direction

It is equivalent to the building style that human eyes can see in front , Each color corresponds to a building height

Such a building height produces a waveform , The topic requirement is to fix the waveform to find the number of building heights that can be increased

Let's take a look at the expected new building height matrix ：

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

The highest floor in each row of the original matrix , The highest floor of each column is ：

 

  The increase of floors is limited by rows , Column maximum value , So the new building height should be its   min( That's ok , Column ) 

Like the first line , That's ok ：8, Compare the columns separately ：9,4,8,7, Minimum value

8,4,87

The second line , That's ok ：7, Compare the columns separately ：9,4,8,7, Minimum value

7,4,7,7

The following is the same , When we find this “ The formula ” after , Code implementation is easy

Method 1 、 Compare the maximum row and column values and take the minimum value

Use a one-dimensional array to store the maximum value of each row ; The maximum value of each column

structure min （ That's ok , Column ） The new matrix of

New matrix elements - Old matrix elements , Cumulative summation is the total increase in height

#define min(a,b) ( (a) < (b) ? (a) : (b) )

void dispRow(int *row, int col)
{
    for(int i=0; i<col; i++)
        printf("disp...row[%d]=%d\n", i, row[i]);
}

void fillMaxrowNum(int *maxrowNum, int **grid, int row, int col)
{
    int max = 0;

    for(int i=0; i<row; i++)
    {
        for(int j=0; j<col; j++)
        {
            if(max < grid[i][j])
                max = grid[i][j];        
        }
        maxrowNum[i] = max;
        max = 0;
    }
}

void fillMaxcolNum(int *maxcolNum, int **grid, int row, int col)
{
    int max = 0;

    for(int j=0; j<col; j++)
    {
        for(int i=0; i<row; i++)
        {
            if(max < grid[i][j])
                max = grid[i][j];        
        }
        maxcolNum[j] = max;
        max = 0;
    }
}

void fillgridNew(int **gridNew, int row, int col, int *maxrowNum, int *maxcolNum)
{
    for(int i=0; i<row; i++)
    {
        for(int j=0; j<col; j++)
        {
            //printf("maxrowNum[%d]=%d, maxcolNum[%d]=%d\n", i, maxrowNum[i], j, maxcolNum[j]);
            gridNew[i][j] = min(maxrowNum[i], maxcolNum[j]);
        }
    }
}

int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
    int num = 0;
    int row = gridSize;
    int col = gridColSize[0];

    int **gridNew = (int **)malloc(sizeof(int *) * row);

    int i, j;
    
    for(i=0; i<row; i++)
    {
        gridNew[i] = (int *)malloc(sizeof(int) * col);
    }

    int *maxrowNum = (int *)malloc(sizeof(int) * col);
    int *maxcolNum = (int *)malloc(sizeof(int) * row);

    fillMaxrowNum(maxrowNum, grid, row, col);
    fillMaxcolNum(maxcolNum, grid, row, col);
    // for(i=0; i<col; i++)
    // {
    //     printf("maxrowNum[%d]=%d\n", i, maxrowNum[i]);
    // }
    // for(i=0; i<row; i++)
    // {
    //     printf("maxcolNum[%d]=%d\n", i, maxcolNum[i]);
    // }

    fillgridNew(gridNew, row, col, maxrowNum, maxcolNum);
    // for(i=0; i<row; i++)
    // {
    //     for(j=0; j<col; j++)
    //     {
    //        printf("gridNew[%d][%d]=%d\n", i, j, gridNew[i][j]);
    //     }
    // }

    for(i=0; i<row; i++)
    {
        for(j=0; j<col; j++)
        {
            num += gridNew[i][j] - grid[i][j];
        }
    }

    free(maxrowNum);
    free(maxcolNum);
    
    for(i=0; i<row; i++)
        free(gridNew[i]);
    free(gridNew);
    
    return num;
}

See more brush notes