Easy

题目描述

给你一个 n × n 的网格 grid，其中放置了一些 1 × 1 × 1 的立方体。每个值 v = grid[i][j] 表示在网格单元格 (i, j) 上放置的立方体塔有 v 个立方体。

在放置这些立方体后，你决定将任何直接相邻的立方体粘在一起，形成几个不规则的 3D 形状。

返回所得形状的总表面积。

注意：每个形状的底面也算入其表面积。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题需要计算由立方体组成的3D形状的表面积。我们可以分别考虑每个立方体塔的贡献。

核心思路： 对于每个位置 (i,j) 上高度为 h 的立方体塔，它的表面积包括：

  1. 上表面和下表面：如果 h > 0，则贡献 2 个单位面积
  2. 四个侧面：每个侧面的面积等于当前塔的高度，但需要减去与相邻塔重叠的部分

计算方法：

  • 对于每个非零高度的塔，初始表面积为 6 * h - 2 * (h-1) = 4*h + 2
  • 然后检查四个方向的相邻塔，减去重叠面积
  • 与右侧塔的重叠面积：min(当前高度, 右侧高度)
  • 与下方塔的重叠面积：min(当前高度, 下方高度)
  • 由于每个重叠面被计算两次，所以每次只减去一次即可

优化思路： 我们可以遍历每个位置，累加其贡献的表面积，对于相邻的立方体，重叠的面积需要减去。为避免重复计算，我们只考虑当前位置与右边和下边相邻位置的重叠。

代码实现

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int n = grid.size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    // 每个立方体塔的基础表面积：6*h - 2*(h-1) = 4*h + 2
                    result += 4 * grid[i][j] + 2;
                    
                    // 减去与右边塔的重叠面积
                    if (j + 1 < n) {
                        result -= 2 * min(grid[i][j], grid[i][j + 1]);
                    }
                    
                    // 减去与下边塔的重叠面积
                    if (i + 1 < n) {
                        result -= 2 * min(grid[i][j], grid[i + 1][j]);
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        result = 0
        
        for i in range(n):
            for j in range(n):
                if grid[i][j] > 0:
                    # 每个立方体塔的基础表面积：6*h - 2*(h-1) = 4*h + 2
                    result += 4 * grid[i][j] + 2
                    
                    # 减去与右边塔的重叠面积
                    if j + 1 < n:
                        result -= 2 * min(grid[i][j], grid[i][j + 1])
                    
                    # 减去与下边塔的重叠面积
                    if i + 1 < n:
                        result -= 2 * min(grid[i][j], grid[i + 1][j])
        
        return result

public class Solution {
    public int SurfaceArea(int[][] grid) {
        int n = grid.Length;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    // 每个立方体塔的基础表面积：6*h - 2*(h-1) = 4*h + 2
                    result += 4 * grid[i][j] + 2;
                    
                    // 减去与右边塔的重叠面积
                    if (j + 1 < n) {
                        result -= 2 * Math.Min(grid[i][j], grid[i][j + 1]);
                    }
                    
                    // 减去与下边塔的重叠面积
                    if (i + 1 < n) {
                        result -= 2 * Math.Min(grid[i][j], grid[i + 1][j]);
                    }
                }
            }
        }
        
        return result;
    }
}

var surfaceArea = function(grid) {
    const n = grid.length;
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                // 每个立方体塔的基础表面积：6*h - 2*(h-1) = 4*h + 2
                result += 4 * grid[i][j] + 2;
                
                // 减去与右边塔的重叠面积
                if (j + 1 < n) {
                    result -= 2 * Math.min(grid[i][j], grid[i][j + 1]);
                }
                
                // 减去与下边塔的重叠面积
                if (i + 1 < n) {
                    result -= 2 * Math.min(grid[i][j], grid[i + 1][j]);
                }
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历整个 n×n 的网格
空间复杂度O(1)只使用了常数额外空间