807. 保持城市天际线 : 简单贪心运用题

简介: 807. 保持城市天际线 : 简单贪心运用题

题目描述



这是 LeetCode 上的 807. 保持城市天际线 ,难度为 中等


Tag : 「贪心」


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


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


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


例子:


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


贪心



根据题意,我们需要确保在调整建筑物高度后,从「水平」和「竖直」两个方向所看到的「行」和「列」的最大高度不变。


因此我们可以先通过 O(n∗m)O(n * m)O(nm) 的复杂度预处理出 grid 中每行的最大值(使用 rrr 数组存储),以及每列的最大值(使用 ccc 数组存储)。


然后在统计答案时,通过判断当前位置 g[i][j]g[i][j]g[i][j]min⁡(r[i],c[j])\min(r[i], c[j])min(r[i],c[j]) 的大小关系来决定当前位置能够增高多少。


可以证明,当每个位置都取得最大的增大高度(局部最优)时,可使得总的增加高度最大(全局最优)。


代码:


class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[] r = new int[n], c = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                r[i] = Math.max(r[i], grid[i][j]);
                c[j] = Math.max(c[j], grid[i][j]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans += Math.min(r[i], c[j]) - grid[i][j];
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(n∗m)O(n * m)O(nm)
  • 空间复杂度:O(n+m)O(n + m)O(n+m)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.807 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
缓存 NoSQL fastjson
Shiro Session集群共享存入Redis中SimpleSession的transient 属性不能序列化
Shiro Session集群共享存入Redis中SimpleSession的transient 属性不能序列化
319 0
|
安全 测试技术
AppScan软件安装说明(上)
AppScan软件安装说明
319 0
|
测试技术 Go 开发工具
【Go语言专栏】Go语言中的代码审查与最佳实践
【4月更文挑战第30天】Go语言因其简洁、高性能及并发能力,在云计算等领域广泛应用。代码审查对提升Go代码质量、遵循规范及团队协作至关重要。审查流程包括提交、审查、反馈、修改和合并代码。工具如GoLand、Git、ReviewBoard和GitHub提供支持。最佳实践包括遵循命名规范、添加注释、保持代码结构清晰、复用代码和确保测试覆盖。积极参与代码审查是提高质量的关键。
266 0
|
机器学习/深度学习 PyTorch 算法框架/工具
|
安全 Python
全局代理IP的工作原理和实现方法
全局代理IP的工作原理和实现方法
282 7
|
网络协议 关系型数据库 MySQL
服务搭建篇(三) 主从Mysql搭建 , 保姆级教程 ,包看包会
而如果要保证数据能够实时同步,对于MySQL,通常就要用到他自身提供的一套通过Binlog日志在多个MySQL服务之间进行同步的集群方案。基于这种集群方案,一方面可以提高数据的安全性,另外也可以以此为基础,提供读写分离、故障转移
190 0
|
Windows Python
MicroPython 玩转硬件系列3:上电自动执行程序
MicroPython 玩转硬件系列3:上电自动执行程序
|
分布式计算 大数据 Shell
大数据开发中常用组件服务的集群管理脚本整理集合
在大数据开发中,需要对各个组件服务集群进行管理,为了效率和可靠性,可以编写shell脚本来统一管理和维护集群,确保系统的稳定性和可靠性。
260 0
|
Rust 安全 Java
谷歌为Android操作系统开发者增加了新的选择 Rust
谷歌为Android操作系统开发者增加了新的选择 Rust
331 0