Trapping Rain Water

最后更新于:2022-04-01 22:56:12

## 一.题目描述 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5ee5bb91.jpg) The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! ## 二.题目分析 该题目需要找到规律。对某个值`height[i]`来说,能trapped的最多的water取决于在`height[i]`之前最高的值:`height[left_max]`和在`height[i]` 的右边的最高值`height[right_max]`。 再简单地说,对于当前值`height[i]` 来说,找到其左边最大值`height[left_max]`和其右边最大值`height[right_max]`,如果: `min(height[left_max], height[right_max]) > height[i]` 那么在`i`这个位置上能trapped的water就是: `min(height[left_max], height[right_max]) - height[i]`。 总结出这个规律后一切就好办了,你可以选择第一遍从左到右遍历,计算数组的`height[left_max]`;第二遍从右到左遍历,计算`height[right_max]`。 这里的方法是先遍历一遍,找到最高的值`height[max_index]`,然后以该值的下标为分界,将数组分为两半,左右分开计算,这样,最大值`height[max_index]` 的左方只需计算各各值左方的最大值;同理 最大值`height[max_index]` 的右方只需计算各各值右方的最大值。 这些方法的时间复杂度是O(n),空间复杂度O(n)。 ## 三.示例代码 ~~~ #include #include using namespace std; class Solution { public: int trap(vector& height) { int n = height.size(); int max_index = 0; // 最高的柱子 for (int i = 0; i < n; ++i) if (height[max_index] < height[i]) max_index = i; int water = 0; // 以最高柱子为界限,左右分开扫描 for (int j = 1, left_max = 0; j < max_index; ++j) { if (height[j] < height[left_max]) water += height[left_max] - height[j]; else left_max = j; } for (int k = n - 2, right_max = n - 1; k > max_index; --k) { if (height[k] < height[right_max]) water += height[right_max] - height[k]; else right_max = k; } return water; } }; ~~~ 结果: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5ee6a9d0.jpg) ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5ee7fc1c.jpg) ## 四.小结 这道题的难点是发现规律,如果做到这一点,实现起来也并不是很难,但以上的方法基本需要遍历两次数组,是否能只用一次遍历就能算出结果而满足空间复杂度限制的方法呢?
';