LeetCode: Trapping Rain Water

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.

这个题的思路应该是,根据当前bar的左右两侧的最高的bar的高度,可以计算出当前bar可以储存的水。

所以用三个循环。第一个从左到右扫描,保存下每个bar左侧最高bar的高度。

第二个从右到左,保存下每个bar右侧最高bar的高度。

最后通过前两个计算出每个bar可以存水多少,加和。

 1 public int trap(int[] A) {
 2         if (A.length == 0) return 0;
 3         int[] left = new int[A.length];
 4         int[] right = new int[A.length];
 5         
 6         int max = A[0];
 7         for (int i=0; i<A.length; i++) {
 8             if (A[i] > max) {
 9                 max = A[i];
10             }
11             left[i] = max;
12         }
13         max = A[A.length-1];
14         for (int i=A.length-1; i>=0; i--) {
15             if (A[i] > max) {
16                 max = A[i];
17             }
18             right[i] = max;
19         }
20         int total = 0;
21         for (int i=0; i<A.length; i++) {
22             int t = Math.min(left[i], right[i]);
23             total += t > A[i] ? t-A[i] : 0; 
24         }
25         
26         return total;
27     }

LeetCode: Trapping Rain Water,,5-wow.com

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