Leetcode 892 Surface Area of 3D Shapes

发表于 |

On a N * N grid, we place some 1 * 1 * 1 cubes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).
Return the total surface area of the resulting shapes.

Example 1:
Input: [[2]]
Output: 10

Example 2:
Input: [[1,2],[3,4]]
Output: 34

Example 3:
Input: [[1,0],[0,2]]
Output: 16

Example 4:
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 5:
Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Note:

  1. 1 <= N <= 50
  2. 0 <= grid[i][j] <= 50

分析：

  1. 根据样例1可以知道这里是需要计算上下底面积的，并且上下底面积是不会被遮盖的，所以每遍历到一个非0的grid[i][j]，结果都需加上2
  2. 然后考虑侧面积，侧面积是有可能被覆盖的，对于一个格子上的柱子，四个侧面被覆盖的面积取决于他周围4个柱子的高度，两者高度取最低值即可。

思路：

  1. 当我们计算周围柱子的时候，可能出现越界的情况，那么这需要单独处理，我们用一个函数处理这种情况，将其视作高度为的柱子，其余照常即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def surfaceArea(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m,n = len(grid),len(grid[0])
        def helper(i,j):
            ans = 0
            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<=x<m and 0<=y<n:
                    ans += max(0, grid[i][j]-grid[x][y])
                else:
                    ans += grid[i][j]
            return ans
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res += 2
                    res += helper(i,j)# 对一个柱子的四周进行分析
        return res

90 / 90 test cases passed.
difficulty: easy
Runtime: 84 ms