807.保持城市天际线

链接：807.保持城市天际线
难度：Medium
标签：贪心、数组、矩阵
简介：在二维数组 grid 中，grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。建筑物高度可以增加的最大总和是多少？。

题解 1 - typescript

• 编辑时间：2021-12-13
• 执行用时：88ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：遍历后存储最大值数组。

function maxIncreaseKeepingSkyline(grid: number[][]): number {
  const n = grid.length;
  const m = grid[0].length;
  const vmax = new Array(m).fill(0);
  const hmax = new Array(n).fill(0);
  let ans = 0;
  for (let row = 0; row < n; row++) {
    let max = 0;
    for (let col = 0; col < m; col++) {
      max = Math.max(max, grid[row][col]);
    }
    hmax[row] = max;
  }
  for (let col = 0; col < m; col++) {
    let max = 0;
    for (let row = 0; row < n; row++) {
      max = Math.max(max, grid[row][col]);
    }
    vmax[col] = max;
  }
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < m; col++) {
      ans += Math.min(vmax[col] - grid[row][col], hmax[row] - grid[row][col]);
    }
  }
  return ans;
}

题解 2 - python

• 编辑时间：2024-07-14
• 执行用时：54ms
• 内存消耗：16.57MB
• 编程语言：python
• 解法介绍：遍历。

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        rows = [0] * n
        cols = [0] * n
        for i in range(n):
            for j in range(n):
                rows[i] = max(rows[i], grid[i][j])
                cols[j] = max(cols[j], grid[i][j])
        return sum(min(rows[i], cols[j]) - grid[i][j] for i in range(n) for j in range(n))