企业官网建设流程全解析

LeetCode-Go 题解 | 807. Max Increase to Keep City Skyline：天际线约束下的最大增高总和

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 807 题Max Increase to Keep City Skyline（保持城市天际线的最大增高）展开，以 LeetCode-Go 仓库中 0807.Max-Increase-to-Keep-City-Skyline 的解题文档为核心骨架，结合仓库内真实 Go 源码与测试用例，完整讲解问题的数学本质、三步式贪心算法、O(n²) 实现细节与复杂度分析。读完本文，你将掌握"如何在不改变任意方向天际线的约束下，最大化建筑增高总和"这一类二维极值问题的通用解法，并能直接复用仓库中的 Go 实现与测试框架。

一、题目回顾：什么是"保持天际线"约束

1.1 英文原题（Problem Statement）

There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrixgridwheregrid[r][c]represents the height of the building located in the block at row r and column c.

A city's skyline is the outer contour formed by all the buildings when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.

Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction.

题目大意（中文）：在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度，高度为 0 的建筑同样可以被增高。最后，从新数组的所有四个方向（顶部、底部、左侧、右侧）观看的"天际线"必须与原始数组的天际线相同。城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。求建筑物高度可以增加的最大总和。

1.2 约束条件（Constraints）

• n == grid.length
• n == grid[r].length（矩阵是 n × n 的方阵）
• 2 <= n <= 50
• 0 <= grid[r][c] <= 100

1.3 关键理解：天际线的数学含义

从某个方向看"天际线"，本质上是该方向投影方向上每一行/每一列的最大值轮廓：

• 从**上方（北）/ 下方（南）**看，天际线由每一列的最大高度决定；
• 从**左侧（西）/ 右侧（东）**看，天际线由每一行的最大高度决定。

因此"不改变任何方向的天际线"，等价于要求：增建之后，每一行的最大值不变、每一列的最大值也不变。

二、示例剖析：结果是如何算出来的

Example 1：

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] Output: 35

原始矩阵：

增建后的矩阵（不改变任意方向天际线的最大结果）：

gridNew = [ [8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ]

验证：

• 每一行的最大值仍然是[8, 7, 9, 3]，左右天际线不变；
• 每一列的最大值仍然是[9, 4, 8, 7]，上下天际线不变；
• 每个格子的增高量累加：(8-3)+(4-0)+(8-8)+(7-4)+(7-2)+(4-4)+(7-5)+(7-7)+(9-9)+(4-2)+(8-6)+(7-3)+(3-0)+(3-3)+(3-1)+(3-0) = 35。

Example 2：

Input: grid = [[0,0,0],[0,0,0],[0,0,0]] Output: 0

全零矩阵的行最大值、列最大值均为 0，任何增高都会改变天际线，因此答案为 0。这个例子验证了边界情况的正确性：当行/列约束上限本身为 0 时，可增高总量为 0。

三、解题思路：两步天际线 + 逐格取小

原文档 README.md 给出的算法步骤非常清晰，共四步：

1. 从数组**竖直方向（顶部、底部）**看"天际线"，计算出topBottomSkyline——即每一列的最大值；
2. 从数组**水平方向（左侧、右侧）**看"天际线"，计算出leftRightSkyline——即每一行的最大值；
3. 计算grid中每个元素与对应的topBottomSkyline和leftRightSkyline中较小值的差值；
4. 统计所有差值的总和ans并返回。

3.1 为什么是"两个天际线中的较小值"？

对于位于(i, j)的建筑，它同时受两个方向的约束：

• 它所在行的天际线高度为leftRightSkyline[i]，因此该格高度不能超过这个值，否则从左侧/右侧看，该行轮廓会被撑高；
• 它所在列的天际线高度为topBottomSkyline[j]，因此该格高度也不能超过这个值，否则从上方/下方看，该列轮廓会被撑高。

为了让"不改变任何方向天际线"且"增高总量最大"，每个格子的上限只能是两者中的较小者：

上限(i, j) = min(leftRightSkyline[i], topBottomSkyline[j])

而每个格子已经有一定高度，所以该格子的最大可增高量为：

可增高量(i, j) = 上限(i, j) - grid[i][j]

对全部 n² 个格子求和即为答案。该做法是贪心思想的体现：对每个格子独立地取到其可行域内最大高度，由于各行、各列约束互不影响地都得到满足，局部最优即全局最优。

3.2 复杂度分析

• 时间复杂度：O(n²)。计算行天际线需要遍历一遍矩阵（O(n²)），计算列天际线需要再遍历一遍（O(n²)），最后累加差值又需要一遍（O(n²)），三遍遍历均为 O(n²)，总复杂度 O(n²)。
• 空间复杂度：O(n)。仅需两个长度为 n 的数组分别存储行天际线与列天际线。

四、Go 源码实现精讲

仓库中该题的官方实现位于 807.Max Increase to Keep City Skyline.go，与文档代码完全一致。下面逐段拆解：

package leetcode func maxIncreaseKeepingSkyline(grid [][]int) int { n := len(grid) topBottomSkyline := make([]int, 0, n) leftRightSkyline := make([]int, 0, n) // 第一步：计算水平方向（左/右）天际线，即每一行的最大值 for i := range grid { cur := 0 for _, v := range grid[i] { if cur < v { cur = v } } leftRightSkyline = append(leftRightSkyline, cur) } // 第二步：计算竖直方向（上/下）天际线，即每一列的最大值 for j := range grid { cur := 0 for i := 0; i < len(grid[0]); i++ { if cur < grid[i][j] { cur = grid[i][j] } } topBottomSkyline = append(topBottomSkyline, cur) } // 第三步：逐格累加 "min(行天际线, 列天际线) - 原高度" var ans int for i := range grid { for j := 0; j < len(grid[0]); j++ { ans += min(topBottomSkyline[j], leftRightSkyline[i]) - grid[i][j] } } return ans } func min(a, b int) int { if a < b { return a } return b }

4.1 代码细节说明

• 行天际线计算：外层循环for i := range grid遍历每一行，内层for _, v := range grid[i]扫描该行所有元素，用cur记录最大值，得到leftRightSkyline[i]。代码对grid的形状没有额外假设，直接用len(grid)与len(grid[0])，保证 n × n 方阵正确。
• 列天际线计算：外层for j := range grid遍历每一列，内层for i := 0; i < len(grid[0]); i++沿列方向扫描，grid[i][j]即以行优先索引访问第 j 列第 i 行的元素，得到topBottomSkyline[j]。
• 累加答案：min(topBottomSkyline[j], leftRightSkyline[i])即该格可达到的最大高度，减去grid[i][j]为该格的最大增高量，全部累加即得最终结果。
• 辅助函数min：仓库在题目包内自带min实现，未依赖外部库；注意题目约束0 <= grid[r][c] <= 100，因此所有差值非负，无需处理负数情况。

从 go.mod 可以看到，仓库模块名为github.com/halfrost/LeetCode-Go，Go 版本为 1.19，题目代码均以package leetcode组织在各自的题目目录下，配合structures、template等工具模块复用。

五、测试用例验证：100% 覆盖的工程化保障

仓库的 807.Max Increase to Keep City Skyline_test.go 使用标准testing框架组织用例，采用para807/ans807结构体封装输入与期望输出：

package leetcode import ( "fmt" "testing" ) type question807 struct { para807 ans807 } // para 是参数 type para807 struct { grid [][]int } // ans 是答案 type ans807 struct { ans int } func Test_Problem807(t *testing.T) { qs := []question807{ { para807{[][]int{{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}}}, ans807{35}, }, { para807{[][]int{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}, ans807{0}, }, } fmt.Printf("------------------------Leetcode Problem 807------------------------\n") for _, q := range qs { _, p := q.ans807, q.para807 fmt.Printf("【input】:%v 【output】:%v\n", p.grid, maxIncreaseKeepingSkyline(p.grid)) } fmt.Printf("\n\n\n") }

用例覆盖了文档给出的两个官方示例：常规 4 × 4 混合矩阵（答案 35）与全零 3 × 3 矩阵（答案 0）。运行go test即可验证实现正确性：

go test ./leetcode/0807.Max-Increase-to-Keep-City-Skyline/...

这种"题目目录 = 源码 + 测试 + 题解文档"的组织方式贯穿整个 LeetCode-Go 仓库（例如 0001.Two-Sum、0015.3Sum 等目录结构一致），便于读者对照源码、测试与解题思路进行学习与回归验证。

六、举一反三：本题的延伸思考

1. 矩阵不一定必须方阵：虽然题目约束为 n × n，但算法本身对 m × n 的矩阵同样成立——行天际线数组长度为 m，列天际线数组长度为 n，只需将len(grid[0])的列数循环与len(grid)的行数循环正确区分即可。
2. 同类"双约束取小"模型：本题与"木桶效应"同构——每个格子的上限由行、列两个方向的瓶颈共同决定。类似思路常见于二维前缀最大/最小约束类问题，如其他涉及行、列独立约束的题目。
3. 正确性的不变量：算法的核心不变量是"增建后行最大值、列最大值与原矩阵完全一致"。以该不变量为切入点，可以推广到"允许降低部分建筑"等变体题设，先求出可行上限矩阵，再计算目标函数极值。

总结

LeetCode 807 题是一道典型的二维约束极值问题，解题链路清晰：先分别提取行、列天际线（两个方向的轮廓），再对每个格子取两个方向约束的较小值作为增建上限，最后累加所有差值。仓库 LeetCode-Go 中该题的 题解文档、Go 实现 与 测试用例 三位一体，给出了可直接运行、可直接验证的完整答案：时间复杂度 O(n²)，空间复杂度 O(n)，代码简洁且边界处理完备，是学习贪心思想与二维数组遍历的优质范例。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go