欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode每日一题:3.25三维形体的表面积(八十二)

程序员文章站 2022-07-02 11:01:29
...

三维形体的表面积

一、LeetCode题解

瞧一瞧~

二、算法题

题目

在 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
};

结果

LeetCode每日一题:3.25三维形体的表面积(八十二)