本文主要是介绍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(高效)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!