【LeetCode】leetcode 807.保持城市天际线

柔光的暖阳◎ 2023-01-15 11:21 134阅读 0赞

## 题目描述： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70]

## 思路： ##

其实是一道很简单的题目，思路在于：求出行列的最大值，他们的最小值与原矩阵中元素的差值即为建筑可以额外加高的高度

求出水平方向的天际线其实很简单，就是每一行的最大值，用列表生成式即可：

row_line = [max(grid[i]) for i in range(len(grid))]

求竖直方向的天际线，可能暴力一点的做法就是：取出原矩阵的每一列，然后取最值。真因为暴力的做法太麻烦，还可能存在超时等一系列问题，想到了一个骚操作：矩阵转置。

原生python的矩阵转置操作可以如下：

grid_t = list(zip(*grid))

这样返回的结果可以实现转置，但是**内部的列表变成了元组**，这点需要注意  
就像这样：  
![在这里插入图片描述][20210422141717737.png]

然后就可以用同样的方法来获取到竖直方向的天际线：

col_line = [max(grid_t[i]) for i in range(len(grid_t))]

之后就是获取到各个元素与其交叉元素的差值了。这里可以放心做差，因为最高的建筑物在交叉时总会与自己做差，所以最后增高的结果是0：

res = 0
    for i in range(len(grid)):
    	for j in range(len(grid[i])):
    		res += min(row_line[i], col_line[j]) - grid[i][j]
            
    return res

如果觉得这样不够优雅，还可以用列表生成式来写：

return sum([min(row_line[i], col_line[j]) - grid[i][j] /
    	for i in range(len(grid)) for j in range(len(grid[i]))])

但是性能会受限：前面二重循环嵌套的写法时间效率可以达到99.68%，空间占用率也不高；数据规模较小时用列表生成式两者差异不大，但是数据规模较大时，时间效率和空间占用也会变大，而且代码阅读起来可读性也很低。所以还是推荐第一种写法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70 2]

## 总结： ##

记录这道题主要是用原生Python实现了矩阵转置

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70]: /images/20221022/3d77de7d32d743e2a7173c67d78a0226.png
[20210422141717737.png]: /images/20221022/f9b5f7eb50344052ad950b6bc21857f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70 1]: /images/20221022/1ac7e01c11d64032a37984111656013d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjkwMDUw_size_16_color_FFFFFF_t_70 2]: /images/20221022/2a4931c91edb45f4b0ed4d298fa21241.png