三维形体投影面积
难度:
标签:
题目描述
在 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].length
1 <= n <= 50
0 <= grid[i][j] <= 50
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用流处理每个平面的投影。
* 2. 对于xy平面的投影,统计每个位置上值大于0的单元格数量。
* 3. 对于yz平面的投影,统计每一列中的最大值。
* 4. 对于zx平面的投影,统计每一行中的最大值。
* 5. 将三个投影的面积相加,得到最终结果。
*/
import java.util.Arrays;
public class Solution {
public int projectionArea(int[][] grid) {
int n = grid.length;
int xyArea = (int) Arrays.stream(grid)
.flatMapToInt(Arrays::stream)
.filter(v -> v > 0)
.count();
int yzArea = Arrays.stream(grid)
.mapToInt(row -> Arrays.stream(row).max().getAsInt())
.sum();
int zxArea = Arrays.stream(grid)
.flatMapToInt(col -> Arrays.stream(col).boxed())
.collect(Collectors.groupingBy(i -> i % n, Collectors.maxBy(Integer::compare)))
.values().stream()
.mapToInt(Optional::get)
.sum();
return xyArea + yzArea + zxArea;
}
}
解释
方法:
本题需要计算三维形体在三个不同的平面上的投影面积。投影面积的计算方法如下:
1. **xy平面投影面积**:所有非零正方体的个数,即每个格子上的正方体数如果大于0,则该格子在xy平面上有投影。
2. **yz平面投影面积**:对每一列,取最大值,这是因为在y轴方向看过去,每列的最高点决定了该列的投影高度。
3. **zx平面投影面积**:对每一行,取最大值,这是因为在x轴方向看过去,每行的最高点决定了该行的投影宽度。
最后,将这三个投影面积相加得到总投影面积。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在计算yz平面投影面积时,为什么选择取每列的最大值而不是其他统计量,比如列的平均值或者求和?
▷🦆
在计算xy平面的投影面积时,你是如何确保只计算非零元素的数量?具体是使用了哪种迭代和条件判断的方式?
▷🦆
使用zip(*grid)进行矩阵转置时,这种方法在大规模数据处理时的性能和内存效率如何?会不会导致内存使用过高?
▷🦆
在实际的代码实现中,你是否考虑过边界情况,比如空的grid或者非常不规则的grid,这些情况会对投影面积的计算产生什么影响?
▷