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

二当家的白帽子 2021-10-27 00:35:24
学习 算法 城市 法学 保持

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

  1. python编写程序, 先输入一组10个元素,再输出数组中比平均值小的所有奇数。
  2. 《用python写网络爬虫》完整版+源码
  3. python中的小问题,友友们来看一下
  4. python自定义函数CircleArea求圆面积
  5. 判断年月日问题python 不知道自己哪里写错了
  6. 关于Python语言表达的问题
  7. Python代码阅读(第23篇):将变量名称转换为短横线连接式命名风格
  8. Python 用ARIMA、GARCH模型预测分析股票市场收益率时间序列
  9. 云计算开发:Python3-encode()方法详解
  10. python编写程序自动计算个人总分平均分各科最高最低平均分
  11. 在不同python版本下的python代码可以集成到一个应用中吗?
  12. 吹弹牛皮之Unity 工具制作常用交互bat ini python
  13. 手动新建和pycharm新建Djagno项目时候,Django项目的文件夹和虚拟环境文件夹venv的位置有所不同
  14. python课提的求解答一下,是什么意思
  15. python画图X轴太密集了,为什么加了代码也没用
  16. 用PYTHON实现EXCEL数据改动的cell高亮显示
  17. Python Type Hints 从入门到实践
  18. 求一个python大大( •︠ˍ•︡ )(想哭)如果可以的话可以开课,我可以去听课
  19. 真香!值得收藏的30道Python练手题(附详细答案)
  20. django+uwsgi+nginx 前后端分离部署配置
  21. 用python实现千图成像工具,快给你的男/女神弄一张吧~
  22. python csv中dwlimiter用不了,有没有大咖能解释一下
  23. 新手学Python要打好哪些基础?从软件安装到全面基础讲解,就它了!
  24. Python中字符串子串的输出
  25. python判断是否一个序列是超增序列
  26. Python爬虫框架的读取和创建
  27. python对数据框中两列进行判断, 得到新的列的
  28. Python做一个模仿文本进度条的编程
  29. python 中使用MS SQL问题 怎样解决
  30. python有没有类似传送门功能的代码,,就是比如这边运行完然后输入一些指令然后可以跳转到程序里的某个地方
  31. Python基操教学!不会?(熟能生巧)
  32. python画图,有没有初学者的代码
  33. 朋友股票亏惨了,我一怒用Python爬取了证券最新数据
  34. 被称之为永远的神!就这6个Python爬虫开源项目?
  35. python Qtreeview 如何选择子行,选择第一行下面的行数
  36. Python随机生成100个1~200之间的不重复数字
  37. 关于#python#的问题,请各位专家解答!
  38. Python编写程序先输入一组10个元素,再输入数组中比平均值小的所有奇数
  39. Ubuntu终端下安装Python需要import的库
  40. 为什么下载pandas和xlwings运行不了,出现No system module pywintypes(系统查不到pywin32具体位置)(又不能重新下载pywin32)
  41. python求带我脱离苦海,哎_
  42. Python 数据分析里面轴的问题
  43. python初学者,请问使用openpyxl库读取文件后出现图片中的报错要怎么解决?
  44. 大学毕业论文写有关python
  45. 授人以鱼吧友友python编写程序自动计算个人总分平均分各科最高最低平均分
  46. python怎么将四行代码换成一行啊
  47. 用Python如何编写啊 真不会啊?
  48. 这个布尔变化怎么做啊(Python
  49. PYTHON求集合交集需要用户手动输入集合名
  50. Python运行哈姆雷特词频统计时出错(如图),是哪方面的问题?
  51. 【Python表白代码合集】”我还是很喜欢你,像风走了八千里,不问归期”!!
  52. python实现学生信息管理系统(含代码)
  53. wxpython中如何按键停止死循环?
  54. python 类的问题?不懂这种方法的作用?不是继承那是什么作用?
  55. Python 题目不会写 求帮助!
  56. Python,turtle制图,要求使用for,while编写
  57. Python题目不会 求帮助! 谢谢您!
  58. Python题目不会!求帮助!
  59. Python这个看不太懂,,大神们帮个忙
  60. 安装拓展库pandas失败怎么解决