LeetCode 题解工作台
三维形体投影面积
在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。 每个值 v = grid[i][j] 表示有一列 v 个正方体叠放在格子 (i, j) 上。 现在，我们查看这些立方体在 xy 、 yz 和 zx 平面上的 投影 。 投影 就像影子，将 三…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·数学
答案摘要
我们可以分别计算三个投影的面积。 - xy 平面的投影面积：每个非零值都会投影到 xy 平面，所以 xy 的投影面积为非零值的个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。
每个值 v = grid[i][j] 表示有一列 v 个正方体叠放在格子 (i, j) 上。
现在，我们查看这些立方体在 xy 、yz 和 zx 平面上的投影。
投影 就像影子，将 三维 形体映射到一个 二维 平面上。从顶部、前面和侧面看立方体时，我们会看到“影子”。
返回 所有三个投影的总面积 。
示例 1：
输入：[[1,2],[3,4]] 输出：17 解释：这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。
示例 2:
输入：grid = [[2]] 输出：5
示例 3：
输入：[[1,0],[0,2]] 输出：8
提示：
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] <= 50
解题思路
方法一：数学
我们可以分别计算三个投影的面积。
- xy 平面的投影面积：每个非零值都会投影到 xy 平面，所以 xy 的投影面积为非零值的个数。
- yz 平面的投影面积：每一行的最大值。
- zx 平面的投影面积：每一列的最大值。
最后将三个面积相加即可。
时间复杂度 ，其中 为网格 grid 的边长。空间复杂度 。
class Solution:
def projectionArea(self, grid: List[List[int]]) -> int:
xy = sum(v > 0 for row in grid for v in row)
yz = sum(max(row) for row in grid)
zx = sum(max(col) for col in zip(*grid))
return xy + yz + zx
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N^2) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate can efficiently compute projections in O(N^2) time.
- question_mark
Candidate uses appropriate methods to calculate max values in rows and columns.
- question_mark
Candidate avoids unnecessary space usage, demonstrating space optimization.
常见陷阱
外企场景- error
Confusing the dimensions of the projections and treating them incorrectly.
- error
Misunderstanding the projection onto the yz- and zx-planes, treating them the same.
- error
Failing to handle edge cases, such as grid size 1x1 or the presence of zero heights.
进阶变体
外企场景- arrow_right_alt
Handle grids of different sizes and edge cases, such as grids with minimum values.
- arrow_right_alt
Extend the problem to higher-dimensional projections, considering additional axes.
- arrow_right_alt
Optimize further for larger grids, testing performance for n up to 50.