807. 保持城市天际线

1. 题目描述
2. 题解

1. 题目描述

https://leetcode.cn/problems/max-increase-to-keep-city-skyline/
在二维数组 $807. 保持城市天际线 - 图1$ 中， $807. 保持城市天际线 - 图2$ 代表位于某处的建筑物的高度。我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。高度 $807. 保持城市天际线 - 图3$ 也被认为是建筑物。
最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。请看下面的例子。
建筑物高度可以增加的最大总和是多少？
例子：

输入： 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] ]

说明:

$807. 保持城市天际线 - 图4$
$807. 保持城市天际线 - 图5$ 的高度范围是： $807. 保持城市天际线 - 图6$ 。
一座建筑物占据一个：换言之，它们是的长方体。
2. 题解
2022-05-02 AC, 就是求出行列的最大值, 然后四个方向可以增加到对应行列的较小高度 ```php <?php /**
- Created by PhpStorm
- User: jtahstu
- Time: 2022/5/2 20:13
- Des: 807. 保持城市天际线
- https://leetcode.cn/problems/max-increase-to-keep-city-skyline/
- 给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的高度。
- 城市的天际线是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的天际线可能不同。
- 我们被允许为任意数量的建筑物的高度增加任意增量（不同建筑物的增量可能不同）。高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度不能影响从任何主要方向观察城市得到的天际线。
- 在不改变从任何主要方向观测到的城市天际线的前提下，返回建筑物可以增加的最大高度增量总和。 */

class Solution {

/**
 * @param Integer[][] $grid
 * @return Integer
 */
function maxIncreaseKeepingSkyline($grid)
{
    $row_max = $col_max = [];
    $n = count($grid);
    //取每行最大值
    foreach ($grid as $r => $rows) {
        $row_max[$r] = max($rows);
    }
    //取每列最大值
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $col_max[$i] = max($col_max[$i] ?? 0, $grid[$j][$i]);
        }
    }
    $count = 0;
    //可以整加到对应行和列较小值的数量
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $count += min($row_max[$i], $col_max[$j]) - $grid[$i][$j];
        }
    }

// print_r($row_max); // print_r($col_max); return $count; } }

var_dump((new Solution())->maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]));

/**

执行用时：20 ms, 在所有 PHP 提交中击败了71.43%的用户
内存消耗：19.3 MB, 在所有 PHP 提交中击败了14.29%的用户
通过测试用例：133 / 133 */ ```

1. 题目描述

2. 题解