892. 三维形体的表面积

在 N N 的网格上，我们放置一些 1 1 * 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

方法一：分步累加

思路

  • 我们单独计算每一个 v = grid[i][j] 所贡献的表面积，再将所有的 v 值相加就能得到最终形体的表面积：
  • 对于顶面和底面的表面积，如果 v > 0 ，那么顶面和底面各贡献了 1 的表面积，总计 2 的表面积；
  • 对于四个侧面的表面积，只有在相邻位置的高度小于 v 时，对应的那个侧面才会贡献表面积，且贡献的数量为 v - nv ，其中 nv 是相邻位置的高度。我们可以将其写成 max(v - nv, 0) 。

举一个例子，对于网格
1 5
6 7
而言，位置 grid[0][1] 的高度为 5：

  • 因为 5 > 0，所以贡献了 2 的顶面和底面表面积；
  • 该位置的上方和右侧没有单元格，可以看成高度为 0，所以分别贡献了 max(5 - 0, 0) = 5 的表面积；
  • 该位置的左侧高度为 1，所以贡献了 max(5 - 1, 0) = 4 的表面积；
  • 该位置的下方高度为 7，所以贡献了 max(5 - 7, 0) = 0 的表面积。

因此 grid[0][1] 贡献的表面积总和为 2 + 5 + 5 + 4 + 0 = 16。

算法

对于每个 v = grid[r][c] > 0 ，计算 ans += 2 ，对于 grid[r][c] 四个方向的每个相邻值 nv 还要加上 max(v - nv, 0) 。

  1. class Solution {
  2.     public int surfaceArea(int[][] grid) {
  3.         int[] dr = new int[]{0, 1, 0, -1};
  4.         int[] dc = new int[]{1, 0, -1, 0};
  6.         int N = grid.length;
  7.         int ans = 0;
  9.         for (int r = 0; r < N; ++r)
  10.             for (int c = 0; c < N; ++c)
  11.                 if (grid[r][c] > 0) {
  12.                     ans += 2;
  13.                     for (int k = 0; k < 4; ++k) {
  14.                         int nr = r + dr[k];
  15.                         int nc = c + dc[k];
  16.                         int nv = 0;
  17.                         if (0 <= nr && nr < N && 0 <= nc && nc < N)
  18.                             nv = grid[nr][nc];
  20.                         ans += Math.max(grid[r][c] - nv, 0);
  21.                     }
  22.                 }
  24.         return ans;
  25.     }
  26. }

方法二：

思路

看看有多少个立方体，总表面积是立方体的数量 × 6，但是因为相邻的会互相盖住，统计一下被盖住的面，然后减去被盖住的面就行了。

  1. class Solution {
  2.     public int surfaceArea(int[][] grid) {
  3.         if(grid == null || grid.length < 1 || grid[0].length < 1) return 0;
  4.         //统计所有的立方体数量
  5.         int blocks = 0;
  6.         //统计有多少个面被其他面盖住，那么就在所有的立方体的表面积上减去被盖住的面数×2（因为盖住一个面需要另一个面来盖，所以会损失2个面）；
  7.         int cover = 0;
  8.         for(int i = 0;i < grid.length;++i) {
  9.             for(int j = 0; j < grid[0].length;++j) {
  10.                 blocks += grid[i][j];
  11.                //这个是统计当前格子中因为堆叠而盖住了几个面
  12.                 cover += grid[i][j] > 1 ? grid[i][j] -1 : 0;
  13.                 if(i > 0) {
  14.                     //看看上一行同一列盖住了多少个面
  15.                     cover += Math.min(grid[i-1][j],grid[i][j]);
  16.                 }
  17.                 if(j > 0) {
  18.                     //看看同一行前一列盖住了几个面
  19.                     cover += Math.min(grid[i][j-1],grid[i][j]);
  20.                 }
  21.             }
  22.         }
  23.         return blocks * 6 - cover * 2;
  24.     }
  25. }