BAT面试算法进阶(9)- 三维形体投影面积

题目

在 N * N 的网格中，我们放置了一些与x，y，z 三轴对齐的 1 * 1 * 1 立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。现在，我们查看这些立方体在xy、yz 和 zx平面上的投影。

投影就像影子，将三维形体映射到一个二维平面上。在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。返回所有三个投影的总面积。

• 例子
• 输入: [[1,2],[3,4]]
• 输出: 17
• 解释: 这里的形状在3个轴对齐平面上的3个投影("阴影部分")

• 提示:
• 1<= grid.length = grid[0].length <=50
• 0 <= grid[i][j] <=50

解决方案

算法思路

• 从顶部看,由该形状生成的阴影将是网格中非零值的数目
• 从侧面看,由该形状生成的阴影将是网格中每一行的最大值
• 从前面看,由该形状生成的阴影将是网格中每一列中的最大值.

例如 [[1,2][3,4]]

• 从顶部的阴影将为4,因为网格中有4个非零值
• 侧面阴影为2+4,因为第一行的最大值为2,第二行的最大值为4
• 前面阴影为3+4,因为第一列的最大值是3,第二列的最大值为4;

代码实现

C++ Code

Java Code

Python Code

复杂度分析

• 时间复杂度:O(N^2),其中N是grid的长度
• 空间复杂度:O(1)

学习建议

• 结合案例图例分析题目
• 结合代码分析计算逻辑

算法面试系列文章：

BAT面试算法进阶(1)--两数之和

BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法)

BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)

BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法)

BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一)

BAT面试算法进阶(6)- BAT面试算法进阶(6)-最长回文子串(方法二)

BAT面试算法进阶(7)- 反转整数

BAT面试算法进阶(8)- 删除排序数组中的重复项

BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)

BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法)

BAT面试算法进阶(12)- 环形链表(哈希表法)