【算法学习】807. 保持城市天际线(java / c / c++ / python / go / rust)

二当家的白帽子 2021-10-27 13:05:56
学习 算法 城市 法学 保持

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



807. 保持城市天际线:

在二维数组grid中,grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量(不同建筑物的数量可能不同)的建筑物的高度。 高度 0 也被认为是建筑物。

最后,从新数组的所有四个方向(即顶部,底部,左侧和右侧)观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时,由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。

建筑物高度可以增加的最大总和是多少?

样例 1

输入:
grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出:
35
解释:
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
从数组竖直方向(即顶部,底部)看“天际线”是:[9, 4, 8, 7]
从水平水平方向(即左侧,右侧)看“天际线”是:[8, 7, 9, 3]
在不影响天际线的情况下对建筑物进行增高后,新数组如下:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]

提示

  • 1 < grid.length = grid[0].length <= 50。
  • grid[i][j] 的高度范围是: [0, 100]。
  • 一座建筑物占据一个grid[i][j]:换言之,它们是 1 x 1 x grid[i][j] 的长方体。

分析

  • 首先要明白天际线是什么:城市的天际线是从远处观看时,由所有建筑物形成的矩形的外部轮廓。影响轮廓的就是你所看方向上,每一行或列上最高的建筑的高度。
  • 所以我们把所看方向上较低的建筑增高到恰好是最高建筑一样的高度,就是在不影响天际线的情况下,建筑物能增加的最大高度。
  • 但是四个方向的天际线都不能影响,思考一下就知道上和下,左和右的天际线是一致的。那么我们只需要在增加建筑物高度的时候,同时考虑2个天际线就可以了,并且我们只能增加到其中较低的高度才能都不影响。
  • 可以分两步,第一步先算出天际线,第二步统计结果。

题解

java

class Solution {

public int maxIncreaseKeepingSkyline(int[][] grid) {

int n = grid.length;
// 算出天际线
int[] rowMaxes = new int[n];
int[] colMaxes = new int[n];
for (int r = 0; r < n; ++r) {

for (int c = 0; c < n; ++c) {

rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// 计算结果
for (int r = 0; r < n; ++r) {

for (int c = 0; c < n; ++c) {

ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}
}

c

int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){

// 算出天际线
int rowMaxes[gridSize];
int colMaxes[*gridColSize];
memset(rowMaxes, 0, sizeof(rowMaxes));
memset(colMaxes, 0, sizeof(colMaxes));
for (int r = 0; r < gridSize; ++r) {

for (int c = 0; c < *gridColSize; ++c) {

rowMaxes[r] = fmax(rowMaxes[r], grid[r][c]);
colMaxes[c] = fmax(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// 计算结果
for (int r = 0; r < gridSize; ++r) {

for (int c = 0; c < *gridColSize; ++c) {

ans += fmin(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}

c++

class Solution {

public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {

int n = grid.size();
// 算出天际线
vector<int> rowMaxes(n, 0);
vector<int> colMaxes(n, 0);
for (int r = 0; r < n; ++r) {

for (int c = 0; c < n; ++c) {

rowMaxes[r] = max(rowMaxes[r], grid[r][c]);
colMaxes[c] = max(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// 计算结果
for (int r = 0; r < n; ++r) {

for (int c = 0; c < n; ++c) {

ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}
};

python

class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
n = len(grid)
# 算出天际线
rowMaxes = [0] * n
colMaxes = [0] * n
for r in range(n):
for c in range(n):
rowMaxes[r] = max(rowMaxes[r], grid[r][c])
colMaxes[c] = max(colMaxes[c], grid[r][c])
ans = 0
#计算结果
for r in range(n):
for c in range(n):
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
return ans

go

func maxIncreaseKeepingSkyline(grid [][]int) int {

n := len(grid)
// 算出天际线
rowMaxes := make([]int, n)
colMaxes := make([]int, n)
for r := 0; r < n; r++ {

for c := 0; c < n; c++ {

rowMaxes[r] = max(rowMaxes[r], grid[r][c])
colMaxes[c] = max(colMaxes[c], grid[r][c])
}
}
ans := 0
// 计算结果
for r := 0; r < n; r++ {

for c := 0; c < n; c++ {

ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
}
}
return ans
}
func max(x, y int) int {

if x > y {

return x
}
return y
}
func min(x, y int) int {

if x < y {

return x
}
return y
}

rust

impl Solution {
pub fn max_increase_keeping_skyline(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
// 算出天际线
let mut rowMaxes = vec![0; n];
let mut colMaxes = vec![0; n];
for r in 0..n {
for c in 0..n {
rowMaxes[r] = rowMaxes[r].max(grid[r][c]);
colMaxes[c] = colMaxes[c].max(grid[r][c]);
}
}
let mut ans = 0;
// 计算结果
for r in 0..n {
for c in 0..n {
ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c];
}
}
return ans;
}
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/


版权声明
本文为[二当家的白帽子]所创,转载请带上原文链接,感谢
https://blog.csdn.net/leyi520/article/details/120911010

  1. python将字符串转成特定列表格式
  2. Python做一个保护手机号编程
  3. 用Spyder运行Python爬虫时仅输出“runfile(xx), wdir=xx”
  4. 使用Python对一组数据进行分段拟合,如何处理断点处的左右倒数相等
  5. Python输出符合条件的文件的路径名
  6. Python中pandas怎么实现分组去重统计和求和
  7. python xpath 爬虫,请帮帮我吧!
  8. python 用泰勒公式近似计算sinx的值 求解代码中哪里出现了错误
  9. Python语法2
  10. python如何将输出的各行数字对齐
  11. 使用 Python 进行数据可视化之Matplotlib
  12. python新鲜题 老公们 救救孩子
  13. 如何用python解答 要如何着手
  14. 请问Python正则表达式如何在多个文本中匹配出关键字
  15. Python 三天打鱼两天晒网问题
  16. mac安装python3
  17. 請問python要怎麼印数字倒等腰三角形
  18. 【算法学习】807. 保持城市天际线(java / c / c++ / python / go / rust)
  19. 【算法学习】237. 删除链表中的节点(java / c / c++ / python / go)
  20. 【算法学习】1512. 好数对的数目(java / c / c++ / python / go / rust)
  21. 【算法学习】1672. 最富有客户的资产总量(java / c / c++ / python / go / rust)
  22. 【算法学习】771. 宝石与石头(java / c / c++ / python / go / rust)
  23. 【算法学习】02.03. 删除中间节点(java / c / c++ / python / go)
  24. 【算法学习】1769. 移动所有球到每个盒子所需的最小操作数(java / c / c++ / python / go / rust)
  25. 【算法学习】1486. 数组异或操作(java / c / c++ / python / go / rust)
  26. 【算法学习】剑指 Offer 64. 求1+2+…+n(java / c / c++ / python / go / rust)
  27. 【算法学习】LCP 44. 开幕式焰火(java / c / c++ / python / go / rust)
  28. 【算法学习】剑指 Offer 58 - II. 左旋转字符串(java / c / c++ / python / go / rust)
  29. python的学校疑问难题求解
  30. 大学python题 作业题 基础题
  31. Python字典的知识,输出的样例为,最高分:89
  32. python写入文件失败且程序提前中止
  33. 用Python写一个学生字典,帮帮忙
  34. Python,能不能帮帮忙,真的不会
  35. [python] yield 和 readline() 的使用问题
  36. python安装找不到问题救救孩子
  37. python中循环结构完成数字游戏
  38. 如何用python实现多列vlookup(excle操作)
  39. python语言deLong‘s test:通过统计学的角度来比较两个ROC曲线、检验两个ROC曲线的差异是否具有统计显著性
  40. LPC55S69 MicroPython模组和库函数
  41. LPC55S69 IoT Kit专属 Micropython模组和库函数简介
  42. 安装LPC55S69 MicroPython模块是遇到的CDC Interface驱动问题
  43. 使用soundcard在Python中操作声卡
  44. 自动化快速上手--Python(7)--【字典】--每天半小时
  45. Python之循环结构【包括列表、for语句、range()函数、while语句、循环嵌套、break、continue、算法优化等】
  46. Python模块安装与异常处理详解(numpy、pygame、matplotlib等)
  47. Python__init__.py作用
  48. python 爬取网页时出现多种错误
  49. Python中关于大量绘制速度曲线的问题
  50. python-async的安装和使用方法
  51. Matlab的fread(fild,1,int32)迁移到python变成什么
  52. 想用python开发一个音频过滤器,请指导?
  53. python使用openpyxl读取Excel文件显示No such file or directory
  54. xmoji虚拟头像交互如何使用python(像深度学习)制作?
  55. python 打开页面页面的链接,为什么总是报错呀?
  56. Python中DataLoader的batch_size、shuffle的疑惑。
  57. python安装pymssql库,可以import,但无法调用函数
  58. 【Python学习教程】常用的8个Python数据可视化库!
  59. python处理csv中的时间
  60. 数据结构,元音统计(Python)