本文為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 ; }

轉載于:https://www.cnblogs.com/jzdwajue/p/7112306.html

總結

以上是生活随笔為你收集整理的Leetcode 动态规划 Trapping Rain Water的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。