Leetcode daily 20/03/26 三维形体的表面积

三维形体的表面积

-题目-

在?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-

??一个1 * 1 * 1的立方体表面积是6。当几个立方体叠放起来，会有一些面被“盖住”，产生表面积的损失。若叠放数量为elem，则网格某个位置的叠放立方体损失self_loss为：

??当某个位置的叠放立方体前后左右有其他叠放立方体，这个叠放立方体和相邻叠放立方体之间也会有一些面被”盖住“，产生表面积的损失。若相邻两个叠放立方体叠放数量分别为elem_1，elem_2，则损失by_loss为：

??因此某位置叠放立方体露出的表面积则为：

-ac代码-

class Solution:

    def _by_loss(self, elem, i_, j_, grid):
        if i_ < 0 or j_ < 0 or i_ >= len(grid) or j_ >= len(grid):
            return 0
        else:
            return min(elem, grid[i_][j_])

    def by_loss(self, elem, i, j, grid):
        return (self._by_loss(elem, i, j + 1, grid)
            + self._by_loss(elem, i, j - 1, grid)
            + self._by_loss(elem, i + 1, j, grid)
            + self._by_loss(elem, i - 1, j, grid)
        )

    def self_loss(self, elem):
        return 2 * (elem - 1) if elem >= 1 else 0

    def surfaceArea(self, grid: List[List[int]]) -> int:
        surface = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                elem = grid[i][j]

                surface += 6 * elem - self.self_loss(elem) - self.by_loss(elem, i, j, grid)

        return surface

-复杂度-

• \(T(n) = O(n^2)\)
• \(S(n) = O(1)\)

Leetcode daily 20/03/26 三维形体的表面积

原文：https://www.cnblogs.com/Chunngai/p/12573531.html