【Leetcode】Trapping Rain Water

浏览数：48 / 时间：2015年06月11日

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. 

 1 class Solution {
 2 public:
 3     int trap(int A[], int n) {
 4         int sum = 0;
 5         int *max_left = new int[n]();
 6         for (int i = 1; i < n - 1; ++i) {
 7             if (A[i - 1] > max_left[i - 1]) {
 8                 max_left[i] = A[i - 1];
 9             } else {
10                 max_left[i] = max_left[i - 1];
11             }
12         }
13         int max_right = 0;
14         for (int i = n - 2; i >= 1; --i) {
15             if (A[i + 1] > max_right) {
16                 max_right = A[i + 1];
17             }
18             if (A[i] < max_left[i] && A[i] < max_right) {
19                 sum += (min(max_left[i], max_right) - A[i]);
20             }
21         }
22         return sum;
23     }
24 };
View Code

单独考虑每根bar，每根bar上方可以盛的水量取决于从它向左扫描到的最高的bar和向右扫描到的最高的bar中较矮的那一个和它本身的高度差。

扫描一遍数组，记录下每根bar左边最高的bar，然后从右向左，一遍记录当前最高的bar，一边计算每根bar上方可以盛水的量，并求和。

【Leetcode】Trapping Rain Water,,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢