LeetCode 807. 保持城市天际线

Categories:

题目描述
思路分析
1. 解法一：行列最大值（推荐）
相似题目

题目描述

✅ 807. 保持城市天际线

思路分析

解法一：行列最大值（推荐）

核心思路：

分别计算每一行和每一列的最大值。

对每个格子，其可增加的高度为 min(rowMax[i], colMax[j]) - grid[i][j]。

累加所有可增加高度即为答案。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 分别表示矩阵行列数。

空间复杂度：O(m + n)，用于行列最大值数组。

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] rowMax = new int[m];
        int[] colMax = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }

        return ans;
    }
}

func maxIncreaseKeepingSkyline(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	rowMax := make([]int, m)
	colMax := make([]int, n)

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] > rowMax[i] {
				rowMax[i] = grid[i][j]
			}
			if grid[i][j] > colMax[j] {
				colMax[j] = grid[i][j]
			}
		}
	}

	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			limit := rowMax[i]
			if colMax[j] < limit {
				limit = colMax[j]
			}
			ans += limit - grid[i][j]
		}
	}

	return ans
}

相似题目

题目	难度	考察点
73. 矩阵置零	中等	矩阵
54. 螺旋矩阵	中等	矩阵
59. 螺旋矩阵 II	中等	矩阵
48. 旋转图像	中等	矩阵
64. 最小路径和	中等	矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/37842631