On a N * N grid, we place some 1 * 1 * 1 cubes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).
Return the total surface area of the resulting shapes.
Example 1:
Input: [[2]]
Output: 10
Example 2:
Input: [[1,2],[3,4]]
Output: 34
Example 3:
Input: [[1,0],[0,2]]
Output: 16
Example 4:
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32
Example 5:
Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46
Note:
1 <= N <= 500 <= grid[i][j] <= 50
这道题给了我们一个二维数组 grid，其中 grid[i][j] 表示在位置 (i,j) 上累计的小正方体的个数，实际上就像搭积木一样，由这些小正方体来组成一个三维的物体，这里让我们求这个三维物体的表面积。我们知道每个小正方体的表面积是6，若在同一个位置累加两个，表面积就是10，三个累加到了一起就是14，其实是有规律的，n个小正方体累在一起，表面积是 4n+2。现在不仅仅是累加在一个小正方体上，而是在 nxn 的区间，累加出一个三维物体。由于之前做过那道三维物体投影的题 Projection Area of 3D Shapes，所以博主很思维定势的想到是不是也跟投影有关，然后又想当然的认为三维物体每一个面的面积就是该方向的投影，那么我们把三个方向的投影之和算出来，再乘以2不就是表面积了么？实际上这种方法是错误的，就拿题目中的例子4来说，当中间的小方块缺失了之后，实际上缺失的地方会产生出四个新的面，而这四个面是应该算在表面积里的，但是用投影的方法是没法算进去的。无奈只能另辟蹊径，实际上这道题正确的思路是一个位置一个位置的累加表面积，就类似微积分的感觉，前面提到了当n个小正方体累到一起的表面积是 4n+1，而这个n就是每个位置的值 grid[i][j]，当你在旁边紧挨着再放一个累加的物体时，二者就会产生重叠，重叠的面数就是二者较矮的那堆正方体的个数再乘以2，明白了这一点，我们就可以从 (0,0) 位置开始累加，先根据 grid[0][0] 的值算出若仅有该位置的三维物体的表面积，然后向 (0,1) 位置遍历，同样要先根据 grid[0][1] 的值算出若仅有该位置的三维物体的表面积，跟之前 grid[0][0] 的累加，然后再减去遮挡住的面积，通过 max(grid[0][0],grid[0][1])x2 来得到，这样每次可以计算出水平方向的遮挡面积，同时还需要减去竖直方向的遮挡面积 min(grid[i][j],grid[i-1][j])x2，这样才能算出正确的表面积，参见代码如下：
class Solution {
public:
int surfaceArea(vector<vector<int>>& grid) {
int n = grid.size(), res = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] > 0) res += 4 * grid[i][j] + 2;
if (i > 0) res -= min(grid[i][j], grid[i - 1][j]) * 2;
if (j > 0) res -= min(grid[i][j], grid[i][j - 1]) * 2;
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/892
类似题目：
参考资料：
https://leetcode.com/problems/surface-area-of-3d-shapes/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
