Easy

题目描述

在一个 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 的正方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在对应格子 (i, j) 上。

现在，我们查看这些正方体在 xy 、yz 和 zx 平面上的投影。

投影 就像影子，将我们的 3 维图形映射到一个 2 维平面上。从顶部、前面和侧面看立方体时，我们会看到"影子"。

返回 所有三个投影的总面积 。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：17
解释：这里有该形体在三个轴对齐平面上的三个投影("阴影部分")。

示例 2：

输入：grid = [[2]]
输出：5

示例 3：

输入：grid = [[1,0],[0,2]]
输出：8

提示：

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

解题思路

这道题需要计算3D形体在三个平面上的投影面积。关键是理解每个投影的几何意义：

xy平面投影（俯视图）：从上往下看，只要某个位置有立方体（grid[i][j] > 0），该位置就会在投影中占据一个单位面积。

yz平面投影（侧视图）：从侧面看，每一行的投影面积等于该行中的最大高度，因为最高的立方体会"遮挡"其他立方体。

zx平面投影（正视图）：从正面看，每一列的投影面积等于该列中的最大高度。

算法步骤：

  1. 遍历整个网格，统计xy平面投影面积（非零格子数）
  2. 计算每行的最大值之和，得到yz平面投影面积
  3. 计算每列的最大值之和，得到zx平面投影面积
  4. 返回三个投影面积的总和

时间复杂度为O(n²)，空间复杂度为O(1)。

代码实现

class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int n = grid.size();
        int xy = 0, yz = 0, zx = 0;
        
        for (int i = 0; i < n; i++) {
            int maxRow = 0, maxCol = 0;
            for (int j = 0; j < n; j++) {
                // xy投影：非零格子
                if (grid[i][j] > 0) xy++;
                
                // yz投影：每行最大值
                maxRow = max(maxRow, grid[i][j]);
                
                // zx投影：每列最大值
                maxCol = max(maxCol, grid[j][i]);
            }
            yz += maxRow;
            zx += maxCol;
        }
        
        return xy + yz + zx;
    }
};

class Solution:
    def projectionArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        xy = yz = zx = 0
        
        for i in range(n):
            max_row = max_col = 0
            for j in range(n):
                # xy投影：非零格子
                if grid[i][j] > 0:
                    xy += 1
                
                # yz投影：每行最大值
                max_row = max(max_row, grid[i][j])
                
                # zx投影：每列最大值
                max_col = max(max_col, grid[j][i])
            
            yz += max_row
            zx += max_col
        
        return xy + yz + zx

public class Solution {
    public int ProjectionArea(int[][] grid) {
        int n = grid.Length;
        int xy = 0, yz = 0, zx = 0;
        
        for (int i = 0; i < n; i++) {
            int maxRow = 0, maxCol = 0;
            for (int j = 0; j < n; j++) {
                // xy投影：非零格子
                if (grid[i][j] > 0) xy++;
                
                // yz投影：每行最大值
                maxRow = Math.Max(maxRow, grid[i][j]);
                
                // zx投影：每列最大值
                maxCol = Math.Max(maxCol, grid[j][i]);
            }
            yz += maxRow;
            zx += maxCol;
        }
        
        return xy + yz + zx;
    }
}

var projectionArea = function(grid) {
    const n = grid.length;
    let xy = 0, yz = 0, zx = 0;
    
    for (let i = 0; i < n; i++) {
        let maxRow = 0, maxCol = 0;
        for (let j = 0; j < n; j++) {
            // xy投影：非零格子
            if (grid[i][j] > 0) xy++;
            
            // yz投影：每行最大值
            maxRow = Math.max(maxRow, grid[i][j]);
            
            // zx投影：每列最大值
            maxCol = Math.max(maxCol, grid[j][i]);
        }
        yz += maxRow;
        zx += maxCol;
    }
    
    return xy + yz + zx;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历整个 n×n 的网格
空间复杂度O(1)只使用常数个额外变量