leetcode-883-Projection-Area-of-3D-Shapes

发表于   |  

描述

On a N * N grid, we place some 1 * 1 * 1cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane.

Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

1
2
Input: [[2]]
Output: 5

Example 2:

1
2
3
4
Input: [[1,2],[3,4]]
Output: 17
Explanation: 
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

shadow

Example 3:

1
2
Input: [[1,0],[0,2]]
Output: 8

Example 4:

1
2
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 14

Example 5:

1
2
Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 21

Note:

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

分析

grid[i][j] 表示在 (x, y) 坐标上的立方体的高度，也就是 z 轴方向上的高度，要求立方体在三个方向的投影的面面积，在 x 固定的情况下，应该求在所有 y 下的节点的立方体的高度的最大值，所有的 x 对应的高度的最大值的和即为 x，z 面的投影。y, z 面的投影同理。对于 x, y 面的投影，只要 z 轴方向上有值就加一。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int projectionArea(int[][] grid) {
        int N = grid.length;
        int result = 0;
        for (int i = 0; i < N; i++) {
            int maxXHeight = 0;
            int maxYHeight = 0;
            for (int j = 0; j < N; j++) {
                if (grid[i][j] > 0) {
                    result++;
                }
                maxXHeight = Math.max(maxXHeight, grid[i][j]);
                maxYHeight = Math.max(maxYHeight, grid[j][i]);
            }
            result += (maxXHeight + maxYHeight);
        }
        return result;
    }
}

题目来源