883. Projection Area of 3D Shapes

On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the  projection  of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane.

Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: [[2]]
Output: 5

Example 2:

Input: [[1,2],[3,4]]
Output: 17
Explanation:
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.


Example 3:

Input: [[1,0],[0,2]]
Output: 8

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 14

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 21

Note:

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

这道题给了我们一个二维数组 grid,用来表示一个 3D 物体形状,表示方法是 grid[i][j] 表示在 (i, j) 位置上的高度,就像垒积木一样,累出了一个三维物体。然后让我们计算三个方向的投影面积之和,所谓的三个方向分别是上方 Top,前方 Front,和侧方 Side。用过一些三维建模软件(例如 Maya, 3DMax)的同学,对这个应该不陌生。我们先来考虑正上方投影面积如何计算,由于题目中说了 grid 数组的宽和高相等,那么上方投影就是一个正方形,前提是每个 grid[i][j] 的值都大于0的话。因为若 grid 数组中有0存在,则表示正方形投影会缺少了一块。由于这个大的正方形投影是由 nxn 个小的正方形组成,那么实际上我们只要统计出小正方形的个数,那么大正方形投影的面积也就知道了(是不有点微积分的感觉)。所以我们在遍历的过程中,只要判断若 grid[i][j] 大于0,则结果 res 自增1即可。下面再来考虑另外两个方向的投影怎么计算,另两个方向的投影的可能是不规则图形,参见题目中给的那个图,如果仔细观察的话,其投影图像的每个阶段的高其实就是各行或各列中的最大值,这也不难理解,就像城市中耸立的高度不同的大楼,若要描出城市的轮廓,那么描出来的肯定都是每个位置上最高建筑物的轮廓。那么问题就变成了累加各行各列的最大值。我们实际上在一次遍历中就能完成,使用了一个小 trick,那就是在第二层 for 循环中,行最大值 rowMax 就是不断用 grid[i][j] 来更新,而列最大值 colMax 就是不断用 grid[j][i] 来更新,巧妙的交换i和j,实现了目标。然后分别把更新出来的行列最大值加到结果 res 中即可,参见代码如下:

class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int n = grid[0].size(), res = 0;
        for (int i = 0; i < n; ++i) {
            int rowMax = 0, colMax = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) ++res;
                rowMax = max(rowMax, grid[i][j]);
                colMax = max(colMax, grid[j][i]);
            }
            res += rowMax + colMax;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/883

参考资料:

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

https://leetcode.com/problems/projection-area-of-3d-shapes/discuss/156726/C%2B%2BJavaPython-Straight-Forward

https://leetcode.com/problems/projection-area-of-3d-shapes/discuss/156771/11-line-1-pass-Java-code-and-explanation-of-the-problem-time-O(N-2)-space-O(1).

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


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation