逻辑算法题，积木接雨水二问题

莫愁
其他
2019-11-23

算法 PHP C语言

简介给定一个 m x n 的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
字数 5325.5

题目

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

说明:

m 和 n 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。

示例：

给出如下 3x6 的高度图:

[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

返回 4。

rainwater_empty

如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

rainwater_fill

下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。

思路

就是将内层数组元素的高度提高到初始数组的最高高度，然后遍历内层的数组元素的上下左右的元素的高度，算出当前元素的最高高度，用while循环遍历，当一个循环内的所有元素的高度都不会变化，则认为已经结束，计算增加的高度及储水量。

代码

PHP

<?php

class Solution
{
    /**
     * @param Integer[][] $$heightMap
     * @return Integer
     */
    public function trapRainWater($heightMap)
    {
        $n = count($heightMap);
        $m = count($heightMap[0]);
        if ($n < 3) {
            return 0;
        } else if ($m < 3) {
            return 0;
        }
        $max_height = 0;
        $newArr = Array();
        for ($i = 0; $i < $n; $i++) {
            $newArr[$i] = Array();
            for ($j = 0; $j < $m; $j++) {
                $newArr[$i][$j] = $heightMap[$i][$j];
                //找出最大值
                if ($heightMap[$i][$j] > $max_height) {
                    $max_height = $heightMap[$i][$j];
                }
                if ($i > 0 && $j > 0 && $i < $n - 1 && $j < $m - 1) {
                    if ($max_height > $heightMap[$i][$j]) {
                        $newArr[$i][$j] = $max_height;
                    }

}
            }
        }

$num_temp = 1;
        $count = 0;

while ($num_temp != 0) {
            $num_temp = 0;
            for ($i = 1; $i < $n - 1; $i++) {
                for ($j = 1; $j < $m - 1; $j++) {
                    $count++;
                    $height = $newArr[$i][$j];
                    $height1 = $heightMap[$i][$j];
                    if ($height == $height1) {
                        continue;
                    }
                    $up = $newArr[$i - 1][$j];
                    $down = $newArr[$i + 1][$j];
                    $left = $newArr[$i][$j - 1];
                    $right = $newArr[$i][$j + 1];
                    if ($height > $up) {
                        if ($up < $heightMap[$i][$j]) {
                            $height = $heightMap[$i][$j];
                        } else {
                            $height = $up;
                        }
                        $num_temp++;
                    }
                    if ($height > $down) {
                        if ($down < $heightMap[$i][$j]) {
                            $height = $heightMap[$i][$j];
                        } else {
                            $height = $down;
                        }
                        $num_temp++;
                    }
                    if ($height > $left) {
                        if ($left < $heightMap[$i][$j]) {
                            $height = $heightMap[$i][$j];
                        } else {
                            $height = $left;
                        }
                        $num_temp++;
                    }
                    if ($height > $right) {
                        if ($right < $heightMap[$i][$j]) {
                            $height = $heightMap[$i][$j];
                        } else {
                            $height = $right;
                        }
                        $num_temp++;
                    }
                    $newArr[$i][$j] = $height;
                }
            }
        }

$num = 0;
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $m; $j++) {
                $num += $newArr[$i][$j] - $heightMap[$i][$j];
            }
        }
        return $num;
    }
}

$Building_blocks = [
    [12, 13, 1, 12],
    [13, 4, 13, 12],
    [13, 8, 10, 12],
    [12, 13, 12, 12],
    [13, 13, 13, 13]
];//14水
$rainwater = new Solution();
$result = $rainwater->trapRainWater($Building_blocks);
echo $result;

C++

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        const int M=heightMap.size();
        if (M < 3)
            return 0;
        const int N=heightMap[0].size();
        if (N < 3)
            return 0;
        vector<vector<int>> water_level(1, vector<int>(N, 0));
        water_level.push_back(vector<int>(N, INT_MAX));
        water_level[1][0] = 0;
        water_level[1][N-1] = 0;
        for (int i=2; i < M-1; ++i)
            water_level.push_back(water_level[1]);
        water_level.push_back(water_level[0]);
        bool flowing = true;
        while (flowing) {
            flowing = false;
            for (int i=1; i < M-1; ++i) {
                for (int j=1; j < N-1; ++j) {
                    const int height = min(
                        max(water_level[i-1][j], heightMap[i-1][j]),
                        max(water_level[i][j-1], heightMap[i][j-1]));
                    if (water_level[i][j] > height) {
                        if (!flowing) flowing = true;
                        water_level[i][j] = height;
                    }
                }
            }
            if (!flowing) break;
            flowing = false;
            for (int i=M-2; i > 0; --i) {
                for (int j=N-2; j > 0; --j) {
                    const int height = min(
                        max(water_level[i+1][j], heightMap[i+1][j]),
                        max(water_level[i][j+1], heightMap[i][j+1]));
                    if (water_level[i][j] > height) {
                        if (!flowing) flowing = true;
                        water_level[i][j] = height;
                    }
                }
            }
        }
        int volumn = 0;
        for (int i=1; i < M-1; ++i) {
            for (int j=1; j < N-1; ++j) {
                if (water_level[i][j] <= heightMap[i][j])
                    continue;
                volumn += water_level[i][j] - heightMap[i][j];
            }
        }
        return volumn;
    }
};

java

class Solution {
    class node{
        int x;
        int y;
        int h;
        public node(int x, int y, int h) {
            this.x = x;
            this.y = y;
            this.h = h;
        }
    }
    public int trapRainWater(int[][] heightMap) {
        PriorityQueue<node> q = new PriorityQueue<>(new Comparator<node>() {
            @Override
            public int compare(node o1, node o2) {
                return o1.h -o2.h;
            }
        });

if(heightMap.length < 3|| heightMap[0].length<3) return 0;
        int row = heightMap.length;
        int col = heightMap[0].length;
        int [][]dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            q.offer(new node(i,0,heightMap[i][0]));
            dp[i][0]=1;
            q.offer(new node(i,col-1,heightMap[i][col-1]));
            dp[i][col-1]=1;
        }
        for (int i = 1; i < col-1; i++) {
            q.offer(new node(0,i,heightMap[0][i]));
            dp[0][i]=1;
            q.offer(new node(row-1,i,heightMap[row-1][i]));
            dp[row-1][i] = 1 ;
        }
        final int [][]dir = {{1,0},{0,-1},{0,1},{-1,0} };
        int res = 0;
        while(!q.isEmpty()){
            node t = q.poll();
            int x = t.x;
            int y = t.y;
            int h = t.h;
            for (int[] ints : dir) {
                int dx = x + ints[0];
                int dy = y + ints[1];
                if(dx <0 ||dx >= row || dy<0||dy>=col || dp[dx][dy]==1)
                    continue;
                if(h> heightMap[dx][dy]){
                    res+=h-heightMap[dx][dy];
                    heightMap[dx][dy] = h ;
                }
                q.add(new node(dx,dy,heightMap[dx][dy]));
                dp[dx][dy] =1;
            }
        }
        return res;

}
}

JavaScript

/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function(heightMap) {
    if(heightMap.length<3){
        return 0;
    }
    else if(heightMap[0].length<3){
        return 0;
    }
    var max_height = 0;
    var newArr = new Array();
    for(var i=0;i<heightMap.length;i++){
        newArr[i]=new Array(); 
        for(var j=0;j<heightMap[i].length;j++){
            newArr[i][j]=heightMap[i][j];
            //找出最大值
            if(heightMap[i][j]>max_height){
                max_height = heightMap[i][j];
            }
            if(i>0&&j>0&&i<heightMap.length-1&&j<heightMap[i].length-1){
                if(max_height>heightMap[i][j]){
                    newArr[i][j]=max_height;
                }

}
        }
    }

另外一个Java思路