题目描述

在 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

算法一

(暴力枚举) $O(n^2)$

枚举每个网格中立方体贡献的表面积 ： 底面 + 侧面

假设该网格中存在立方体，且高度H

• 底面 ： 上下两个面 贡献 1 + 1 = 2
• 侧面 ： 分别计算4个侧面贡献的表面积
  • (1) 侧面没有和其他立方体接触 ，贡献 H * 1 = H
  • (2) 侧面有和其他立方体接触，且接触的立方体的高度为h
    • 如果 H > h， 则恭喜啊H -h
    • 如果 H < h， 则被覆盖，贡献为 0

复杂度

时间复杂度：O(N^2)O(N 2)，其中 NN 是 grid 中的行和列的数目。

空间复杂度：O(1)O(1)。

C++ 代码

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        // 定义 每格立方体侧面接触的立方体 的方向 前 右 后 左
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        int n = grid.size();
        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 new_i = i + dx[k];
                        int new_j = j + dy[k];
                        int new_v = 0;        
                        // 侧面接触到的其他立方体的高度 ；首先初始化为0 假定不存在

                        if(new_i >=0 && new_i < n && new_j >= 0 && new_j < n)  // 判断是否有接触
                            new_v = grid[new_i][new_j];      //如有则更新高度

                        res += max(grid[i][j] - new_v , 0); 
                        // 有接触则且高于对方  或者 无接触 则有贡献，否则 无贡献，即贡献为0
                    }
                }
            }

        return res;

    }
};