LeetCode892-三维形体的表面积

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/surface-area-of-3d-shapes/

中文链接：https://leetcode-cn.com/problems/surface-area-of-3d-shapes/

题目详述

在 N N 的网格上，我们放置一些 1 1 * 1 的立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。

请你返回最终形体的表面积。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

题目详解

方法一：直接计算所有不重叠的面积。

  • 枚举每一个点，首先加上上下两面的面积。
  • 然后枚举上下左右四个方向，加上不重叠的面积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LeetCode_00892 {

    int[] dirs = {-1, 0, 1, 0, -1};

    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    res += 2;                                               // 上下两面
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dirs[k], y = j + dirs[k + 1];
                        if (x >= 0 && x < n && y >= 0 && y < n) {
                            res += Math.max(0, grid[i][j] - grid[x][y]);    // 比周围高的部分
                        } else {
                            res += grid[i][j];                              // 边缘部分
                        }
                    }
                }
            }
        }
        return res;
    }
}

方法二：先计算总面积，再减去重叠的部分。

  • 枚举每一个点，首先加上这个小长方体的表面积。
  • 然后减去与前面长方体重叠的面积、与左边长方体重叠的面积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00892 {

    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    res += 2 + grid[i][j] * 4;                              // 总的表面积
                    if (i > 0) {
                        res -= Math.min(grid[i][j], grid[i - 1][j]) * 2;    // 减去与前面重叠的面积
                    }
                    if (j > 0) {
                        res -= Math.min(grid[i][j], grid[i][j - 1]) * 2;    // 减去与左边重叠的面积
                    }
                }
            }
        }
        return res;
    }
}