经典算法实例应用：三维形体投影面积

我们先来看题目描述在 n x n 的网格 grid 中我们放置了一些与 xyz 三轴对齐的 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解决方案方法一数学思路和算法根据题意x 轴对应行y 轴对应列z 轴对应网格的数值。因此xy 平面的投影面积等于网格上非零数值的数目yz 平面的投影面积等于网格上每一列最大数值之和zx 平面的投影面积等于网格上每一行最大数值之和。返回上述三个投影面积之和。代码Javaclass Solution { public int projectionArea(int[][] grid) { int n grid.length; int xyArea 0, yzArea 0, zxArea 0; for (int i 0; i n; i) { int yzHeight 0, zxHeight 0; for (int j 0; j n; j) { xyArea grid[i][j] 0 ? 1 : 0; yzHeight Math.max(yzHeight, grid[j][i]); zxHeight Math.max(zxHeight, grid[i][j]); } yzArea yzHeight; zxArea zxHeight; } return xyArea yzArea zxArea; } }复杂度分析时间复杂度O(n2)其中 n 是网格的行数或列数。空间复杂度O(1)。