Trapping Rain Water

浏览数：22 / 时间：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 public class Solution {
 2     public int trap(int[] A) {
 3         int len = A.length;
 4         if(len<2) return 0;
 5         int []leftMax = new int[len], rightMax = new int[len];
 6         int max=0;
 7         max = A[0];
 8         leftMax[0] = 0;
 9         for(int i=1;i<len;i++){
10             leftMax[i] = max;
11             if(A[i]>max){
12                 max = A[i];
13             }
14         }
15         max = A[len-1]; 
16         rightMax[len-1]=0;
17         int trap = 0;
18         for(int i=len-2;i>=0;i--){
19             rightMax[i] = max;
20             if(max<A[i]){
21                 max = A[i];
22             }
23             if(Math.min(rightMax[i],leftMax[i])-A[i]>0){
24                 trap+=Math.min(rightMax[i],leftMax[i])-A[i];
25             }
26         }
27         return trap;
28     }
29 }
View Code

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

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

相关文章

随机文章

您可能还喜欢

您可能还喜欢