LeetCode-42.接雨水

42.接雨水

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

**输入：**height = [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 个单位的雨水（蓝色部分表示雨水）。

/****************************
* 列遍历方法
* 1:假设每一个位置都有一个宽度为1的桶
* 2:那么如果想计算接水数，需要用左边最高的，减去右边最高的，
*   即可获得当前位置所接到的雨水数
* 3:还需要减去当前位置的高度，才是当前位置最终可以接到的雨水数
*****************************/
int trap(vector<int>& height)
{//1:获取左/右遍历当前位置最大值数组，int result = 0;int n = height.size();vector<int> left_max(n);vector<int> right_max(n);//获取左遍历，第i位置的最大值left_max[0] = height[0]; for (int i = 1; i < n; i++){left_max[i] = max(left_max[i-1], height[i]);}//获取右遍历，第i位置的最大值right_max[n - 1] = height[n - 1];for (int i = n-2; i > 0; i--){right_max[i] = max(right_max[i+1], height[i]);}//取第i位置左右最大值的最小值，减去当前位置高度，等于可接水数量for (int i = 1; i < n-1; i++){result += min(left_max[i], right_max[i])-height[i];}return result;
}

最新原创的文章都先发布在公众号，欢迎关注哦~，
扫描下方二维码回复「资料」可以获得我汇总整理的计算机学习资料~