LeetCode每日一题：3.25三维形体的表面积（八十二）

三维形体的表面积

一、LeetCode题解

瞧一瞧～

• 博健的LeetCode题解：Gitbook版本传送门
• 博健的LeetCode题解：CSDN传送门
• 有趣的CSS：Gitbook传送门
• 前端进阶笔记：Gitbook传送门

二、算法题

题目

在 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

解法一 （动态规划）

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

思路

核心思想：dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])

1. 定义arr[i]表示前第i个预约，记录第i个预约的时长
2. 接预约之前，都会保留当前最优解

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var surfaceArea = function(grid) {
    let r = grid.length, c = grid[0].length
    let surface = 0
    for(let i=0; i<r; i++){
        for(let j=0; j<c; j++){
            let temp = grid[i][j]
            if(temp > 0){
                surface += 4*temp +2
                if(j<c-1 && grid[i][j+1] > 0) surface -= Math.min(temp, grid[i][j+1])
                if(i<r-1 && grid[i+1][j] > 0) surface -= Math.min(temp, grid[i+1][j])
                if(i>0 && grid[i-1][j] > 0) surface -= Math.min(temp, grid[i-1][j])
                if(j>0 && grid[i][j-1] > 0) surface -= Math.min(temp, grid[i][j-1])
            }
        }
    }
    return surface
};

结果