LeetCode #892 三维形体的表面积

本贴最后更新于 1323 天前,其中的信息可能已经东海扬尘

892.png

Problem Description

N * N 的网格上,我们放置一些 1 * 1 * 1 的立方体。

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

请你返回最终形体的表面积。

note

  • 1 <= N <= 50
  • 0 <= grid[i][j] <= 50

e.g.

  • 示例 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
  • 示例 5:
    • 输入:[[2, 2, 2], [2, 1, 2], [2, 2, 2]]
    • 输出:46

Solution

这题是#883 三维形体投影面积的升级版几何题目,883 这题描述的利用一个二维数组的元素代表单个单元格的高度按照从左向右的顺序在 xy 平面上从上到下堆叠,求 xy、yz、xz 三个投影面积。

883 这题相对简单,投影面积就是求最大值,因为矮的会被高的「覆盖」,只要求三个面即可。

示例图:

892projection1.png

但是 889 这题就复杂了很多,他需要的是整个形体的表面积,而非投影面积。于是就带来了一个问题,被挡住的柱状形体可能存在表面积。

一开始我思考的是按照 883 的方式,还是先求出 6 个面(整个形体)的投影面积,再加上「凹陷」的表面积即可。因为只有存在「凹陷」情况,才会多出一部分表面积,但是所谓的“正证法”,会遇到的情况就十分多样了。

比如:

  1. [[1, 0, 1]][1, 0, 0, 1]
  2. [[1, 0], [0, 2]]

当凹陷是 2 个单位时或者 0 的情况等等这些情况就比较复杂,凹陷的判断十分的纷繁凌乱,感觉这个办法就很蠢。

在题解中看到了一个“阿姨”的方法,属实 8 错。他的思路是把所有柱子作为一个单位,求出所有柱子的表面积,如:1 的表面积是 1 * 4 + 2 为 6,2 的表面积是 2 * 4 + 2 为 10,再减去柱子与柱子之间相贴的面积。

给阿姨倒一杯卡布奇诺。

892projection2.png

892projection3.png

所以,当我们遍历整个形体时,只要判断该柱子与「上面」和「左边」是否有接触,有接触且不为 0(为 0,即柱子不存在,也不会出现遮挡的情况)的话,就减去较矮的那个柱子的高度 * 2,因为是两面相贴,所以要乘以 2。

Java 代码如下:

public static int surfaceAreaPro(int[][] grid) {
    int fucker = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            // ① 柱子为0,则整个为0
            fucker += (4 * grid[i][j] == 0 ? -2 : 4 * grid[i][j]) + 2;

            // ②
            if (i - 1 >= 0 && grid[i - 1][j] != 0 && grid[i][j] != 0) {
                fucker -= Math.min(grid[i][j], grid[i - 1][j]) * 2;
            }
            // ③
            if (j - 1 >= 0 && grid[i][j - 1] != 0 && grid[i][j] != 0) {
                fucker -= Math.min(grid[i][j], grid[i][j - 1]) * 2;
            }
        }
    }
    return fucker;
}

另外说明一点,这样写更简洁,但是效率还可以提升,提升在哪呢?因为当前柱子高度为 0 的时候,直接跳过即可。可是如上这样写即使当前柱子高度为 0,①②③ 这三步都会走一遍会影响效率,但是看起来更简洁就 vans 了。

  • 几何
    2 引用 • 18 回帖
  • 算法
    388 引用 • 254 回帖 • 22 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖
1 操作
matthewhan 在 2020-07-03 10:49:44 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...