LeetCode 7. 三维形体的表面积

摘要：

题目：

在 $N \times N$ 的网格上，我们放置一些 $1 \times 1 \times 1$ 的立方体。
每个值 $v = grid[i][j]$ 表示 $v$ 个正方体叠放在对应单元格 $(i, j)$ 上。
请你返回最终形体的表面积。

示例1：

输入：[[2]]
输出：10

示例2：

输入：[[1,2],[3,4]]
输出：34

示例3：

输入：[[1,0],[0,2]]
输出：16

示例4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32

示例5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46

提示：

• $1 <= N <= 50$
• $0 <= grid[i][j] <= 50$

---

用示例5举例，二维数组 [[2,2,2],[2,1,2],[2,2,2]]：

• Java

int[][] grid = {
    {2, 2, 2},
    {2, 1, 2},
    {2, 2, 2}
};

表明一个 $3 \times 3$ 网格，每个格子分别放置对应数字的方块。
那么，表面积 $=$ 总数 $\times 6 - 2(x + y + z)$，其中 $x$, $y$, $z$ 分别表示 $x$, $y$, $z$ 方向重叠面数

• Java

class Solution {
    public int surfaceArea(int[][] grid) {
        // this surface means hidden surface
        int surfaceZ = 0, surfaceY = 0, surfaceX = 0;
        // value count
        int value = 0;
        for (int raw = 0; raw < grid.length; raw++) {
            for (int column = 0; column < grid[raw].length; column++) {
                // count value
                value += grid[raw][column];
                // for each X, Y ,Z count hidden surface
                if (raw < grid.length - 1)
                    surfaceX += Math.min(grid[raw][column], grid[raw+1][column]);
                if (column < grid[raw].length - 1)
                    surfaceY += Math.min(grid[raw][column], grid[raw][column+1]);
                if (grid[raw][column] > 0)
                    surfaceZ += (grid[raw][column] - 1);
            }
        }
        // this surface is real "surface"
        int surface = 0;
        surface = value * 6 - surfaceX * 2 - surfaceY * 2 - surfaceZ * 2;
        return surface;
    }
}

• 时间复杂度：$O(N^2)$，其中 $N$ 是 $grid$ 中的行和列的数目
• 空间复杂度：$O(1)$

原题链接： LeetCode 7. 三维形体的表面积