Leetcode 042 Trapping Rain Water（高效）

本文主要是介绍Leetcode 042 Trapping Rain Water（高效），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Leetcode 042 Trapping Rain Water

解题思路：从左向右遍历一遍，保存每个位置往左的最高值。再从右往左遍历一遍，保存每个位置往右的最高值。最后遍历一遍数组，取左右最高值中较小的一个，减去当前值，即为这个位置增加的量。

class Solution {public:int trap(vector<int>& height) {int n = height.size(), h;int* l = new int[n];int* r = new int[n];h = 0;for (int i = 0; i < n; i++) {h = max(h, height[i]);l[i] = h;}h = 0;for (int i = n-1; i >= 0; i--) {h = max(h, height[i]);r[i] = h;}int ans = 0;for (int i = 0; i < n; i++)ans += min(l[i], r[i]) - height[i];delete l;delete r;return ans;}
};

这篇关于Leetcode 042 Trapping Rain Water（高效）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---