题目描述

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

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

返回结果形体的总表面积。

样例

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

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

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

注意

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

算法

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

1. 逐一枚举每个非 0 的格子，上下两面对答案的贡献总共为 2；
2. 然后再遍历这个格子周围的 4 个格子，对于每个方向，假设高度为 h，则对答案的贡献为 max(0, grid[i][j] - h)；若这个格子在边界，则在边界的面上直接加上 grid[i][j] 即可。其原理就是除去挡住的部分。

时间复杂度

• 枚举所有的格子，故时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int n = grid.size();

        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};

        int ans = 0;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0)
                    continue;

                ans += 2;

                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || x >= n || y < 0 || y >= n) {
                        ans += grid[i][j];
                    }
                    else {
                        ans += max(0, grid[i][j] - grid[x][y]);
                    }
                }
            }
        return ans;
    }
};