本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個?n * n?的網(wǎng)格?grid?，上面放置著一些?1 x 1 x 1?的正方體。每個值?v = grid[i][j]?表示?v?個正方體疊放在對應(yīng)單元格?(i, j)?上。

放置好正方體后，任何直接相鄰的正方體都會互相粘在一起，形成一些不規(guī)則的三維形體。

請你返回最終這些形體的總表面積。

注意： 每個形體的底面也需要計入表面積中。

示例 1：

輸入：grid = [[1,2],[3,4]]
輸出：34

示例 2：

輸入：grid = [[1,1,1],[1,0,1],[1,1,1]]
輸出：32

示例 3：

輸入：grid = [[2,2,2],[2,1,2],[2,2,2]]
輸出：46

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] <= 50

這一題和HDU 5538類似，也和LeetCode 463. Island Perimeter完全相同。

解法 直接遍歷+容斥原理

本題求的是疊方塊的表面積，每個位置上的立方體（疊放的多個正方體）沒有和周邊立方體重疊時，本身表面積為 $6\times h?(h?1)\times 2$（每個正方體貢獻(xiàn)了 $6$ 個表面積、再減去多個正方體重疊的面）。簡化一下就是 $4\times h+2$（考慮上底和下底面，以及每個正方體貢獻(xiàn)的 $4$ 個側(cè)表面）。

再通過從左上到右下遍歷，判斷下方和右邊是否有重疊的立方體，如果有重疊，計算當(dāng)前立方體的表面積時，要減去 $2\times \min (grid[i+1][j],grid[i][j])$ （下方有重疊），$2\times \min (grid[i][j+1],grid[i][j])$ （右側(cè)有重疊），即可得到最終結(jié)果。

class Solution {
    public int surfaceArea(int[][] grid) {
        int ans = 0;
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0) continue;
                // ans += grid[i][j] * 6 - (grid[i][j] - 1) * 2;
                ans += (grid[i][j] << 2) + 2;
                if (i + 1 < n && grid[i + 1][j] != 0) // 右邊
                    ans -= Math.min(grid[i][j], grid[i + 1][j]) << 1;
                if (j + 1 < m && grid[i][j + 1] != 0) // 下邊
                    ans -= Math.min(grid[i][j], grid[i][j + 1]) << 1;
            }
        }
        return ans;
    }
}

復(fù)雜度分析：

• 時間復(fù)雜度：$O(mn)$
• 空間復(fù)雜度：$O(1)$

似乎還可稍作優(yōu)化。上面的代碼在循環(huán)中做了太多次乘法/移位操作，可將這些操作放到最后進(jìn)行。
作為改進(jìn)，整體思路是看看有多少個立方體，總表面積是立方體的數(shù)量 $\times 6$ ，但上下疊放的正方體、和相鄰的立方體會互相遮蓋住，統(tǒng)計一下被蓋住的面，最后減去被蓋住的面就行：

class Solution {
    public int surfaceArea(int[][] grid) {
        int blocks = 0, cover = 0; // 正方體的個數(shù),蓋住的面的個數(shù)
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0) continue; 
                blocks += grid[i][j];
                cover += grid[i][j] - 1;
                if (i + 1 < n && grid[i + 1][j] != 0) // 右邊
                    cover += Math.min(grid[i][j], grid[i + 1][j]);
                if (j + 1 < m && grid[i][j + 1] != 0) // 下邊
                    cover += Math.min(grid[i][j], grid[i][j + 1]);
            }
        }
        return blocks * 6 - cover * 2;
    }
}

復(fù)雜度分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-495786.html

• 時間復(fù)雜度：$O(mn)$
• 空間復(fù)雜度：$O(1)$

到了這里，關(guān)于LeetCode 892. Surface Area of 3D Shapes【數(shù)組,數(shù)學(xué)】簡單的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！