TNotes.leetcode

Appearance

0892. 三维形体的表面积【简单】

0892. 三维形体的表面积【简单】 ​

1. 📝 题目描述 ​

给你一个 n * n 的网格 grid，上面放置着一些 1 x 1 x 1 的正方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。

放置好正方体后，任何直接相邻的正方体都会互相粘在一起，形成一些不规则的三维形体。

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

注意：每个形体的底面也需要计入表面积中。

示例 1：

img

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

示例 2：

img

txt
输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：32

示例 3：

img

txt
输入：grid = [[2,2,2],[2,1,2],[2,2,2]]
输出：46

提示：

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

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number[][]} grid
 * @return {number}
 */
var surfaceArea = function (grid) {
  const N = grid.length
  let area = 0

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (grid[i][j] > 0) {
        // 顶面和底面
        area += 2 // 每个柱子顶和底各1

        // 四个方向的侧面
        const directions = [
          [-1, 0],
          [1, 0],
          [0, -1],
          [0, 1],
        ]
        for (const [di, dj] of directions) {
          const ni = i + di
          const nj = j + dj
          let neighborHeight = 0
          if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
            neighborHeight = grid[ni][nj]
          }
          // 当前柱子在该方向上暴露的高度 = 当前高度 - 与邻居重叠部分
          area += Math.max(grid[i][j] - neighborHeight, 0)
        }
      }
    }
  }

  return area
}
js
/**
 * @param {number[][]} grid
 * @return {number}
 */
var surfaceArea = function (grid) {
  const N = grid.length
  let totalArea = 0

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      // 每个立方体贡献6个面
      totalArea += grid[i][j] * 6

      // 减去垂直堆叠造成的遮挡
      // 每个堆叠点遮挡2个面（上下两个面）
      if (grid[i][j] > 0) {
        totalArea -= (grid[i][j] - 1) * 2
      }

      // 减去与相邻立方体之间的遮挡
      // 上方向邻居
      if (i > 0) {
        totalArea -= Math.min(grid[i][j], grid[i - 1][j]) * 2
      }

      // 左方向邻居
      if (j > 0) {
        totalArea -= Math.min(grid[i][j], grid[i][j - 1]) * 2
      }
    }
  }

  return totalArea
}
  • 时间复杂度：O(n2)，遍历每个格子
  • 空间复杂度：O(1)
  • 解题思路-1：查 4 个面
    • 总表面积 = 所有立方体的顶面 + 底面 + 四个侧面暴露的部分
    • 顶面和底面：只要该位置有立方体，就各贡献 1 面 → 所以每个非零格子贡献 2。
    • 侧面（前后左右）：每个方向的暴露面积 = 当前格子高度 - 与邻居重叠部分（即与邻居的较小高度）
  • 解题思路-2：查 2 个面
    • 计算相邻面数量
    • 每个立方体贡献 6 个面，但堆叠在一起时，每相邻两个立方体会遮挡 2 个面（上面和下面）。
    • 同时，在相邻格子之间（前后左右），也会因为高度重叠而遮挡侧面。
    • 综上，算法如下：
    • 先计算所有立方体的总表面积（不考虑遮挡）：6 * 每个格子的高度
    • 然后减去被遮挡的面：
      • 垂直堆叠遮挡：每个格子内部，height - 1 个接触面，每个遮挡 2 个面（上下），所以减去 2 * (height - 1)
      • 相邻格子之间的遮挡：对每个方向（上下左右），取两个格子的最小高度，乘以 2（因为两个面被遮挡）
  • 对比：
    • 思路 1 是计算每根立柱的四周有效面积 - 周围的 4 个面都要查
    • 思路 2 是根据规律，利用 6 个面减去每个被遮挡面的数量的两倍得到结果 - 遮挡面只需要查每个立方体的两个面（比如俯视图的左上角）

Discussions