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

莫愁
其他
2019-11-22

简介给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
字数 1897.5

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

从图中分析，我们发现能接到水的坐标两边都比该坐标上的积木高，这样才能接上水。我们可以分别找出左边右边最高位置，然后根据最短的是极限接水高度来计算该段可以接多少。

坐标是0的积木为H(0)，他左边最高的积木是L(0)，右边最高的是R(3)，所以该处可以接max(L(0),R(3))-H(0) = 0,

坐标是1的积木为H(1)，他左边最高的积木是L(0)，右边最高的是R(3)，所以该处可以接max(L(0),R(3))-H(1) = -1，由于接的水不能是负数，所以结果是0,

坐标是2的积木为H(0)，他左边最高的积木是L(1)，右边最高的是R(3)，所以该处可以接max(L(1),R(3))-H(0) = 1，

坐标是3的积木为H(2)，他左边最高的积木是L(1)，右边最高的是R(3)，所以该处可以接max(L(1),R(3))-H(2) = -1，由于接的水不能是负数，所以结果是0,

坐标是4的积木为H(1)，他左边最高的积木是L(2)，右边最高的是R(3)，所以该处可以接max(L(2),R(3))-H(1) = 1，

坐标是5的积木为H(0)，他左边最高的积木是L(2)，右边最高的是R(3)，所以该处可以接max(L(2),R(3))-H(0) = 2，

坐标是6的积木为H(1)，他左边最高的积木是L(2)，右边最高的是R(3)，所以该处可以接max(L(2),R(3))-H(1) = 1，

坐标是7的积木为H(3)，他左边最高的积木是L(2)，右边最高的是R(2)，所以该处可以接max(L(2),R(2))-H(3) = -1，由于接的水不能是负数，所以结果是0,

坐标是8的积木为H(2)，他左边最高的积木是L(3)，右边最高的是R(2)，所以该处可以接max(L(3),R(2))-H(2) = 0，

坐标是9的积木为H(1)，他左边最高的积木是L(3)，右边最高的是R(2)，所以该处可以接max(L(3),R(2))-H(1) = 1，

坐标是10的积木为H(2)，他左边最高的积木是L(3)，右边最高的是R(1)，所以该处可以接max(L(3),R(1))-H(2) = -1，由于接的水不能是负数，所以结果是0,

坐标是11的积木为H(1)，他左边最高的积木是L(3)，右边最高的是R(0)，所以该处可以接max(L(3),R(0))-H(1) = -1，由于接的水不能是负数，所以结果是0,

上面加起来就是0+0+1+0+1+2+1+0+0+1+0+0=6;

代码思路

上面思路就是找每个积木数的左边和右边最高的积木数，代码实现如下。

PHP代码:

class BuildingBlocks_water_tarp 
{
    /**
     * @param Integer[] $height
     * @return Integer
     */
    public function cal($height) {
        $result = 0;
        $len = count($height);
        $height_array = array();
        $max = 0;
        $i = 0;
        /*
         * 思路 从左边开始循环积木块，找比他大的那一块的高度
         * */
        for (; $i < $len; $i++) {
            $height_array[$i][0] = $height[$i];
            if ($height[$i] >= $max) {
                $max = $height[$i];
                $height_array[$i][1] = 0;
            } else {
                $height_array[$i][1] = $max;
            }
        }

$max = 0;
        $i = $len - 1;

for (; $i >= 0; $i--) {
            if ($height[$i] >= $max) {
                $max = $height[$i];
                $height_array[$i][2] = 0;
            } else {
                $height_array[$i][2] = $max;
            }
        }

$min = 0;
        $i = 0;

for (; $i < $len; $i++) {
            if ($height_array[$i][0] < $height_array[$i][1] && $height_array[$i][0] < $height_array[$i][2]) {
                $min = $height_array[$i][1] > $height_array[$i][2] ? $height_array[$i][2] : $height_array[$i][1];
                $result += ($min - $height_array[$i][0]);
            }
        }
        
        return $result;
    }
}

进一步思考，我们其实可以简化成这样：

C++代码:

C代码：

其他编程语言大家仿照这个思路来编写，一定会成功的！

该函数时间效率是O(n)，空间是O(1)。已经是该问题最优的解法了。