开发者社区> abcccccccccccccccccccccccccode> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

3D接雨水2(leetcode)——Java实现(又是想上吊的一天)

简介: 给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。以下的内容回答你的疑惑和困难。
+关注继续查看

本以为今天有是平平的一天,结果早上起床,说突发疫情,停止线下课,然后十分开心。打开leetcode准备每日一题,结果给我做到自闭,一度想放弃!!接下来就让我们看一看这样的题。。。有多么恶心


给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。


示例 1:

image.png



输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]


输出: 4


解释: 下雨后,雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:


image.png


输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]


输出: 10


提示:

m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104


废话不多说,先上代码,再解释,如果你做不出来,那你看看你光代码能看懂吗?

class Solution {
    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0) return 0;
        int n = heights.length;
        int m = heights[0].length;
        // 用一个vis数组来标记这个位置有没有被访问过
        boolean[][] vis = new boolean[n][m];
        // 优先队列中存放三元组 [x,y,h] 坐标和高度
        PriorityQueue pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        // 先把最外一圈放进去
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    pq.offer(new int[]{i, j, heights[i][j]});
                    vis[i][j] = true;
                }
            }
        }
        int res = 0;
        // 方向数组,把dx和dy压缩成一维来做
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            // 看一下周围四个方向,没访问过的话能不能往里灌水
            for (int k = 0; k < 4; k++) {
                int nx = poll[0] + dirs[k];
                int ny = poll[1] + dirs[k + 1];
                // 如果位置合法且没访问过
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
                    // 如果外围这一圈中最小的比当前这个还高,那就说明能往里面灌水啊
                    if (poll[2] > heights[nx][ny]) {
                        res += poll[2] - heights[nx][ny];
                    }
                    // 如果灌水高度得是你灌水后的高度了,如果没灌水也要取高的
                    pq.offer(new int[]{nx, ny, Math.max(heights[nx][ny], poll[2])});
                    vis[nx][ny] = true;
                }
            }
        }
        return res;
    }
}


讲一下解题思路,


如果要存水,那么它的上下左右就必须要比它高才可以


我们先从最外层数组开始,找最低(小)的一个位置开始切入,为什么要这样做呢?因为木桶效应,就是能存多少水由最短的木板决定,超过最短就会溢出了。只要最外层够高那么不管里面有多么复杂,只要内层有位置水都可以存。所以最关键的就是最外层的最低处。


我们就是将整个数组当作木桶来处理的,只不过这个木桶里面有很多大石头而已。从最外层最低处开始判断,它的上下左右比它大还是小。


如果比它大那就说明这个内层(上下左右位)存不了水,就更新整个木桶的最外围,其他位置不变,将这个原来最低的地方换成比它大的内层做最外围;

如果比它小,那就说明可以存水,把比它小的内层(上下左右)填充水至与它同高,接下来再把这些填充过的内层作为最外围;


它的上下左右不是比它大就是比它小,但是不管比它大还是比它小,只要遍历了这个最低处都会更新桶的最外围,然后重新找最低处,继续判断最低处的上下左右,继续更新桶的最外围,直到遍历过所有的位置为止。


每一次遍历,它都会标记已经遍历过的数组防止重复


代码不长,但是处处都是精华哇


这里用到了优先队列,方向数组和三元数组,如果你不知道,我帮你找好了,你去看看再回来继续:-------> 优先队列详解和方向数组详解和三元数组


这里用的是优先队列来储存它们的位置,所以每次poll出来的都是最低位置的数组元素位置,还非常巧妙的用到了方向数组来遍历它的上下左右位置的数组元素


看到这里你就可以回去看看代码了,懂了之后真的是十分有意思!!


大家遇到难题千万不要轻易放过啊,因为你早晚还会遇到它的,有可能就是面试时候哦~


如果还有不懂的,可以和我私聊一起探讨!


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
时间轮-Java实现篇
在前面的文章《[时间轮-理论篇](https://developer.aliyun.com/article/910513)》讲了时间轮的一些理论知识,然后根据理论知识。我们自己来实现一个简单的时间轮。
501 0
采用linux下java http实现下载功能
[root@luozhonghua javacode]# vi getHttpResource.java [root@luozhonghua javacode]# cat getHttpResource.java /**   http获取文件   luozhonghua */ import java.io.*; import java.net.*; public class
1829 0
java实现MsOffice文档向pdf文档转化
本篇文档实现功能,将word和ppt文档的文件转化成pdf格式的文档 应用到jacob   第一步:下载压缩包 (1)jacob官网下载jacob压缩包 (2)网址:http://sourceforge.
1010 0
java编程排序之内置引用类型的排序规则实现,和自定义规则实现+冒泡排序运用
第一种排序:【冒泡排序】基本数据类型的排序。 【1】最简易的冒泡排序。效率低。因为比较的次数和趟数最多。 1 /** 2 * 最原始的冒泡排序。 3 * 效率低。
1650 0
java中Comparable实现对象的比较
/* class A implements Comaprable{ } 那么 A x = new A(); 类关系图 Object o = A; Object Compa...
639 0
java简单的实现搜索框的下拉显示相关搜索功能
最近做了一个简单的搜索框下面下拉显示相关搜索的功能,有点模仿百度的下拉展示相关搜索   先上个展示图 : 点击进入演示地址,大家可以输入长点的搜索,点击搜索,再输入之前搜索词的前面部分,看是否能展示出来   搜索框相关搜索的展示很简单,就是根据你的搜索词,去数据库中匹配,是否有类似的搜索词存...
1537 0
文章排行榜
最热
最新
相关电子书
更多
Java开发者面试百宝书
立即下载
Java高级特性入门(二)
立即下载
云栖社区特邀专家徐雷Java Spring Boot开发实战系列课程(第20讲):经典面试题与阿里等名企内部招聘求职面试技巧
立即下载