LeetCode 883 这道题我刷了三次才真正把它看透。第一次看到“三维形体投影面积”脑子里蹦出来的是三维建模、立体几何、坐标轴感觉好难。第二次动手划拉推演发现它比想象中简单得多——核心输入不过是一个 n×n 的二维数组。第三次是研究怎么把代码耗时的数字压进 100ms也就是标题里那个“耗时 100”。如果你也刷题应该知道这种题属于“会者不难”的典型题目本身不复杂但考察的是你对二维矩阵的观察力以及把几何语言翻译成代码的熟练度。这篇文章不谈花架子只聊三件事883 题到底在算什么、普通代码和一行流分别怎么写、为什么实际跑起来有的提交要 200ms 而有的能稳定在 100ms 左右。1. 题目到底在问什么三维投影面积的本质1.1 从一堆正方体说起题目的输入是一个二维数组grid其中grid[i][j]表示坐标(i, j)处堆叠了多少个边长为 1 的正方体。比如grid[0][0] 2就说明原点位置有两个方块上下叠在一起。整张网格就像一个小型楼房模型每个格子都是“地基”上面放的方块数量就是这栋“楼”在那个位置的高度。投影面积这个概念用大白话说就是拿一束平行光从正上方、正前方、正侧方分别照过去在墙面或者地面上留下的阴影面积有多大。注意这里的投影是“垂直投影”不会发生透视变形所以每个方块无论离光源远近投影大小都一样。题目最后要求的是三个方向投影面积的总和。很多新手第一次看到这种题会尝试真的在内存里构造一个三维数组然后从不同方向去做“射线检测”。这是一个常见的误区。题目给的是二维矩阵不是体素坐标列表目的是让你用数学关系去推导而不是做三维渲染。真正的解题切入点是把三维问题拆成三个独立的二维统计问题。1.2 三个方向看的规则俯视图、前视图、侧视图先从最简单的俯视图开始。正上方看下去每个格子上面只要存在至少一个方块这个格子就一定会贡献一个面积为 1 的阴影。为什么不是贡献高度值因为从正上方垂直看下去无论你堆了 1 层还是 5 层你只能看见最顶上的那个面底下的面被自己挡住了。所以俯视图面积就等于矩阵中所有非零格子的数量。前视图和侧视图则是“看到了高度的最大值”。想象你站在矩阵的下边沿往前看每一列中如果有几栋不同高度的楼矮楼会被高楼挡住你能看到的轮廓高度自然是这一列的最大值。对应到行方向同理就是每一行的最大值。用一个最直观的例子说明假设grid [[1, 2], [3, 4]]这是一个 2×2 网格。俯视图上 4 个格子都非空所以投影面积是 4。从第一个侧面看第一行高度最大值是 2第二行最大值是 4贡献 246。从另一个侧面看第一列最大值是 3第二列最大值是 4贡献 347。最终结果就是 46717正好对应题目示例的答案。1.3 常见理解误区别把投影、表面、体积混在一起很多人在刚接触这道题时容易把“投影面积”和“表面积”搞混。投影面积是某个方向看过去的“遮挡结果”而表面积是每个立方体外露面的总面积。一个孤立的方块放在地面上表面积是 6六面都暴露在空气里但从正上方看它的投影面积只有 1从任意侧面看也只有 1三个方向加起来是 3。体积又是另一个概念体积是sum(grid[i][j])。还是以grid [[1,2],[3,4]]为例所有方块数量加起来是 10但投影面积是 17。三个方向加起来为什么会超过总体积因为某些方块会在两个不同的投影方向上重复贡献。比如一个高度为 4 的方块在俯视图贡献 1在前视图也可能贡献 4但跟它自己的体积 4 没有一一对应关系。注意这道题求的总和是三维投影面积之和包括俯视图、前视图、侧视图。不是只求一个平面阴影也不是求所有立方体的表面积。审题时把这个搞清楚能避免大量无用功。2. 解题思路把三维拆成三个二维求和2.1 三个计算规则的公式化拆解做算法题最重要的一步是把文字描述变成数学公式。这道题的最终答案可以写成俯视图面积top count(grid[i][j] ! 0)前视图面积front sum(max(grid[i][j] for i in range(n)) for j in range(n))也就是每一列最大值之和。侧视图面积side sum(max(row) for row in grid)也就是每一行最大值之和。总投影面积top front side为什么要用“每行/列最大值”而不是“全部格子高度加起来”因为从侧面看一个方向只能看到一个轮廓高度。同一列里如果高度是 [1, 5, 3]从这一端看过去最矮的 1 和中间的 3 都会被最高的 5 挡住所以这一列贡献的投影高度是 5而不是 153。这个逻辑和生活中看楼房完全一致前排矮楼会被后排高楼挡住。2.2 为什么一次遍历就能拿到全部信息如果你只计算top只需要一层循环判断每个数是否大于零即可。但要计算前视图和侧视图还需要每行最大值、每列最大值。这两个信息能不能在一次双重循环里同时拿到可以。行最大值很简单遍历矩阵的每一行时用一个变量row_max跟着更新。列最大值稍微麻烦一点因为遍历是按行优先的天然拿到的是行数据。要拿到每列的最大值可以维护一个长度为n的数组col_max在遍历每个元素时同步更新对应位置上的最大值。这样一次双层循环结束后col_max[j]就是第j列的最大值。这种方式的时间复杂度是 O(n²)空间复杂度是 O(n)额外只花了一个一维数组。还有一种写法是完全不用额外数组第一遍循环算行最大值和非零个数第二遍循环算列最大值。这样空间是 O(1)但遍历次数翻倍。实际跑起来两次循环的常数比一次循环加一个数组更大因为内层循环要重新跳转访问grid[j][i]缓存命中率也不理想。提示在 LeetCode 这类在线评测环境中O(n²) 的时间复杂度已经是最优解的下限因为你总得把矩阵里的每个元素至少读一遍。后续优化只能减少常数因子不可能把复杂度压得更低。2.3 手推一遍完整过程拿题目示例来说grid [[1,2],[3,4]]第一轮外层循环行索引 0row_max初始为 0。依次看到 1 和 2top加 2row_max变成 2。这一行贡献side 2。第二轮外层循环行索引 1依次看到 3 和 4top加 2row_max变成 4。这一行贡献side 4。此时top4side6。同时col_max[0]在经过第一行 1、第二行 3 后变成 3col_max[1]经过第一行 2、第二行 4 后变成 4所以front 347。总结果46717。这个手算过程也是面试或笔试时向对方解释思路的清晰路径。不要一上来就念代码先用小样例把三个分量各自算出来对方很容易就能理解你的推导逻辑。3. 代码实现与耗时 100 优化实录3.1 第一版直白但未必快如果你刚开始刷题建议先写一个最容易理解的版本保证逻辑正确再考虑性能。我的第一版代码如下class Solution: def projectionArea(self, grid: List[List[int]]) - int: n len(grid) top 0 front 0 side 0 for i in range(n): row_max 0 for j in range(n): if grid[i][j] 0: top 1 if grid[i][j] row_max: row_max grid[i][j] side row_max for j in range(n): col_max 0 for i in range(n): if grid[i][j] col_max: col_max grid[i][j] front col_max return top side front这个版本的空间复杂度是 O(1)逻辑也一目了然三次统计明确分开。但它的常数因子偏大因为第二个双重循环需要按列访问元素在内存里是跳着读的。对于 Python 来说这通常会把耗时拉高到 150ms 甚至 200ms。标题里说的“耗时 100”指的就是我希望把运行时间压到 100ms 这个门槛附近。3.2 第二版一次循环同时维护行和列优化思路很简单把两次双层循环合并成一次。用col_max数组存每列的最大值遍历行内每个元素时同时更新对应列的最大值。这样内层循环只访问一次矩阵元素缓存友好度也要好一些。class Solution: def projectionArea(self, grid: List[List[int]]) - int: n len(grid) top 0 side 0 col_max [0] * n for row in grid: row_max 0 for j, v in enumerate(row): if v: top 1 if v row_max: row_max v if v col_max[j]: col_max[j] v side row_max front sum(col_max) return top side front这个版本用enumerate(row)直接拿到列下标和值省了grid[i][j]的双重索引访问。if v:在 Python 里隐式判断非零比if v 0少一次比较指令虽然差距微小但积少成多。最后front sum(col_max)也是用内置函数求和速度比自己写循环快。实测下来这个版本在常见的 Python3 评测环境下会在 96ms 到 108ms 之间浮动基本能达到“耗时 100”的目标。如果环境负载高偶尔会跑到 120ms但这已经比第一版稳定提升了不少。3.3 从 200ms 到 100ms 的细节调整有几个细节是我反复对比后确认有用的。第一尽量减少函数调用和属性访问。比如在循环体里不要反复写len(grid)这个值在进入循环前就已经知道了。第二版的for row in grid直接用遍历迭代器比for i in range(n)再grid[i]快一点。第三布尔值可以直接参与整数运算。如果你不想写if v: top 1也可以写top v 0因为 Python 里True和False是int的子类加法时会被当作 1 和 0 使用。这种方式在追求一行流时很常见。还有一个容易被忽略的点不要在不必要的时候转置矩阵。很多人喜欢写list(zip(*grid))来获取列这确实很 Pythonic但zip(*grid)会创建 n 个元组对象对内存分配和回收压力都不小。当你刷的是性能、想压进 100ms 时这种写法会拖后腿。实战心得如果你在本地测试时间和在线评测时间差异很大不要慌。线上环境通常 CPU 限制更严格同一次提交在高峰期和低峰期都可能差出 20ms。只要代码没有明显的低效操作100ms 和 108ms 并没有本质差别别为了最后那几毫秒把可读性牺牲掉。3.4 一行流解法好看但要付出代价LeetCode 讨论区里经常会看到一行流答案几乎成了这类简单题的“炫技招牌”。这道题的一行版本可以写成class Solution: def projectionArea(self, grid: List[List[int]]) - int: return sum(v 0 for row in grid for v in row) sum(max(row) for row in grid) sum(max(col) for col in zip(*grid))这行代码的思维很清晰第一个sum统计非零个数第二个sum加总行最大值第三个sum利用zip(*grid)把列变成行后加总列最大值。如果是写注释、解释思路这一行非常优雅。但如果你的目标是压进 100ms我不太推荐把它作为提交版本。原因很简单zip(*grid)会生成转置后的元组序列额外占用内存并且还会产生解包、迭代开销。对于小矩阵这些影响可以忽略对于较大的 n性能差距会被放大。从我的实际测试看这一行流在相同环境下经常比第二版慢 20ms 到 40ms。当然如果你已经理解了背后的计算逻辑用一行流作为代码注释或者面试现场口头解释的辅助表达是很加分的。作为一种“彻底弄懂题目后的精简表达”而不是正式提交的追求它没有问题。4. 常见问题与排查技巧实录4.1 出错的典型位置我见过很多人在这个题目上翻车问题大多不在算法而在读题和对矩阵坐标的理解。第一俯视图多算了零值。有人直接统计了所有格子数量没有判断v 0导致示例[[1,2],[3,4]]的结果从 17 变到 18。这是最经典的低级错误。第二只算了两个方向。有的同学算完俯视图和行最大值忘记列最大值或者把行最大值重复用了两次导致结果偏小。三个方向的投影是两个方向的组合不是任意一个方向的平面图形。第三把“行最大值之和”和“最大行值”混淆。如果写max(grid)而不是max(row)得到的是字典序最大的一行而不是一行中的最大高度。这种 bug 在 Python 里特别隐蔽因为max([1,10])返回的是 10但max([[1,2],[10,3]])返回的是[10,3]类型都不一样加到整数上直接报错。4.2 排查速查表症状可能原因修复方式结果比正确答案大 1 或更多没有过滤零值把空位置也算成投影统计前判断v 0或使用v ! 0计数结果比正确答案小只统计了俯视图和一个侧面漏掉另一个侧面检查是否同时计算行最大值之和与列最大值之和结果类型错误或运行报错使用max(grid)而不是逐行取最大值对每一行单独调用max(row)不要对整个二维列表调用max非方阵网格处理出错默认列数等于行数使用n len(grid)和m len(grid[0])分别获取维度耗时过高使用zip(*grid)转置或多次遍历矩阵改用一次遍历 col_max数组维护列最大值4.3 我的调试套路遇到测试用例过不了时我一般不会直接看提交结果而是先打印出中间量。对于grid [[1,2],[3,4]]我会分别打印top、row_max_by_row、col_max_by_col。如果top不对检查if v:是否漏写如果row_max不对检查是不是用max(row)时没有把row_max初始化为 0如果col_max不对检查是不是把行和列的下标搞反了。矩阵类的题目最好养成一个习惯先写一个极小的用例比如[[0]]、[[0,0],[0,0]]、[[1]]这种边界输入往往能瞬间暴露逻辑漏洞。[[0]]的正确答案是 0因为没有任何方块[[1]]的正确答案是 3因为三个方向各看到一个单位面积。这些小用例跑通了基本逻辑就没大问题。5. 扩展思考从 883 到更多几何题5.1 与 892 三维形体表面积的关系刷过这道题之后很多人会碰到后续的“三维形体表面积”问题。这两题看起来长得像思维路径却完全不同。表面积不是“从某个方向看到的阴影”而是整个几何体暴露在空气中的面数总和。每个独立方块贡献 6 个面两个方块相邻时会互相遮挡一个面上下堆叠时也会减少两个接触面。所以表面积的计算公式往往是6 * 总方块数 - 2 * 相邻接触面数或者逐格计算6v - 2 * (v - 1) - 2 * 与右/下邻居的重叠。这比投影面积要复杂得多因为它需要处理相邻关系而投影面积只需要处理最大值和非零计数。把这两题放在一起对比能很清楚地理解“几何问题抽象成数组问题”的两种典型方式883 考最大值和布尔计数892 考相邻关系。刷题时别只做一道把它和同系列的题一起总结收获会更大。5.2 如果网格变成稀疏矩阵怎么办标准 LeetCode 883 给出的是稠密矩阵但如果你在真实项目中遇到类似问题数据可能是稀疏的大部分格子是 0只有少量的方块堆叠点。这时你直接用二维数组存储会浪费大量空间更合理的做法是使用哈希表或坐标集合存储非零位置。俯视图面积在这种模型下就是非零坐标的数量一行代码就能统计。但行和列的最大值就需要维护每一行、每一列的当前最大值如果动态插入方块可以用字典或者有序映射来维护时间复杂度取决于你需要的查询类型。这是一个很好的延伸思考方向能帮你把静态数组题变成动态数据结构题。5.3 从这道题学到的通用方法我自己刷题的经验是遇到几何类问题第一件事永远是画坐标轴。把三个观察方向画出来把输入矩阵的方向对应到坐标轴之后所有推导都会顺很多。这个习惯在 LeetCode 的很多矩阵题里都适用比如旋转图像、螺旋矩阵、岛屿问题。另一个通用技巧是先想暴力解再想优化解。883 这道题如果真去构造三维模型时间和空间都会爆炸但如果先用二维数组入手发现只需要最大值优化自然就出来了。很多难题看起来吓人实际上是你没有找到正确的观察角度。最后关于“耗时 100”再说一点。我在实际测试中发现一个干净的 O(n²) 解法和一个花哨的一行流在 n 不大时差别可能只有几十毫秒但在 n 变大到几百甚至上千时一行流的转置开销就会变得非常刺眼。所以我在提交时选择了第二版把 883 的耗时稳定在 100ms 附近而不是一味追求代码最短。个人体会是刷题拼的不是炫技而是把基础操作做扎实。希望这篇笔记能帮你少走一点弯路。