跳至正文

每日一题——807. 保持城市天际线

807. 保持城市天际线

有一个由n x n个街区组成的城市,每个街区都有一个单独的建筑,形状像一个垂直的方形棱柱。你会得到一个0索引的n x n整数矩阵网格,其中网格[r][c]表示位于block中r行和c列的建筑的高度。

一个城市的天际线是所有建筑从远处看城市侧面所形成的外部轮廓。从每个主要方向的天际线可能是不同的东西南北方向。

我们允许任意数量的建筑增加任意数量的高度(每个建筑的高度可以不同)。零高度建筑物的高度也可以增加。然而,增加建筑物的高度不应该从任何主要方向影响城市的天际线。

返回在不改变城市天际线的任何基本方向的情况下建筑物高度可以增加的最大总和。

public class Solution {
    public int MaxIncreaseKeepingSkyline(int[][] grid) {
        int[] rowMax = new int[grid[0].Length];
        int[] columnMax = new int[grid[0].Length];

        for(int i = 0;i < grid[0].Length;i++)
        {
            for(int j = 0;j < grid[0].Length;j++)
            {
                rowMax[i] = Math.Max(rowMax[i],grid[i][j]);
                columnMax[j] = Math.Max(columnMax[j],grid[i][j]);
            }
        }

        int ans = 0;
        for(int i = 0;i < grid[0].Length;i++)
        {
            for(int j = 0;j < grid[0].Length;j++)
            {
                ans += Math.Min(rowMax[i],columnMax[j]) - grid[i][j];
            }
        }
        return ans;
    }
}

看懂了题目其实不难(虽然我没有一遍过)

你会发现大家的思路其实都差不多

定义一个行的最大值的数组

定义一个列的最大值的数组

遍历第一遍把行和列的最大值分别存储到两个数组里

遍历第二遍,先得出行最大值和列最大值哪个值最小

然后把当前位置的高度补满到这个最小值

最后累加就能得到结果了

发表评论

您的电子邮箱地址不会被公开。