Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 892. Surface Area of 3D Shapes #892

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 892. Surface Area of 3D Shapes #892

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

@grandyang grandyang commented May 30, 2019

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 <= 50
  • 0 <= 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 同步地址:

#892

类似题目:

Projection Area of 3D Shapes

参考资料:

https://leetcode.com/problems/surface-area-of-3d-shapes/

https://leetcode.com/problems/surface-area-of-3d-shapes/discuss/163414/C%2B%2BJava1-line-Python-Minus-Hidden-Area

LeetCode All in One 题目讲解汇总(持续更新中...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.