题目描述

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

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

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

例子：
输入： 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] 的长方体。

来源：LeetCode

思路

遍历一次找到竖直方向和水平方向的天际线，即每行和每列的最大元素是多少。
再遍历一次将每个建筑增加到该行和该列天际线中的较小值。合计每次增加的高度，即为结果。

这里是存在办法只遍历一次就计算出结果的。只是做题时，夜已经挺深了，思路总是理不清，而且那样解答代码理解难度也将增加，于是作罢。
以后再说吧。🤠

解法

/**
 * @param {number[][]} grid
 * @return {number}
 */
const maxIncreaseKeepingSkyline = grid => {
  let rise = 0;
  const rowSkyline = Array(grid[0].length).fill(0);
  const colSkyline = Array(grid.length).fill(0);

  grid.forEach((row, i) => {
    row.forEach((building, j) => {
      if (building > rowSkyline[j]) {
        rowSkyline[j] = building;
      }

      if (building > colSkyline[i]) {
        colSkyline[i] = building;
      }
    });
  });

  grid.forEach((row, i) => {
    row.forEach((building, j) => {
      rise += Math.min(rowSkyline[j], colSkyline[i]) - building;
    });
  });

  return rise;
};