您当前位置：首页 > 互联网 > Leetcode 动态规划 Trapping Rain Water

Leetcode 动态规划 Trapping Rain Water

来源：程序员人生发布时间：2014-09-19 17:34:07 阅读次数：3470次

本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie

Trapping Rain Water

Total Accepted: 14568 Total Submissions: 50810My Submissions

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.

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!

题意：有一个代表 n 根柱子高度的数组A[i]，计算这些柱子之间的槽能够储蓄的最大水量
思路：左右 dp
用一个数组 left[i] 表示第 i 根柱子左边最高的柱子的高度
用一个数组 right[i] 表示第 i 根柱子右边最高的柱子的高度
1.从左到右扫描，left[i] = max(left[i - 1], A[i - 1])
2.从右到左扫描，right[i] = max(right[i + 1], A[i + 1])
3.第 i 根柱子上能储蓄的水为 min(left[i], right[i]) - A[i]，因为这时 left[i] 已经没用了，可以用它来存放这个值。
复杂度：时间O(n)，空间O(n)

相关题目：

Candy

int trap(int A[], int n){ if (n == 3) return 0; vector<int> left(n, 0), right(n, 0); for(int i = 1; i < n - 1; ++i) left[i] = max(left[i - 1], A[i - 1]); for(int i = n - 2; i > 0; --i) { right[i] = max(right[i + 1], A[i + 1]); left[i] = min(left[i], right[i]) - A[i]; } int sum = 0; for_each(left.begin() + 1, left.end() - 1, [&sum](int c){ if(c > 0) sum += c; }); return sum ; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 工信部发首批11张虚拟运营商牌照开发者有哪些新机会

下一篇 火速围观，AMD APU新芯片架构A68H呼之欲出！

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点