1+ /*
2+ Author: King, higuige@gmail.com
3+ Date: Oct 07, 2014
4+ Problem: Trapping Rain Water
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/trapping-rain-water/
7+ Notes:
8+ Given n non-negative integers representing an elevation map where the width of
9+ each bar is 1, compute how much water it is able to trap after raining.
10+ For example,
11+ Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
12+
13+ Solution: 1. Find left bound and right bound for each element. O(n).
14+ 2. more space efficiency. Time: O(n), Space: O(1);
15+ */
16+ public class Solution {
17+ public int trap_1 (int []A ) {
18+ int n =A .length ;
19+ if (n ==0 )return 0 ;
20+ int []maxLeft =new int [n ];
21+ int []maxRight =new int [n ];
22+ maxLeft [0 ] =A [0 ];
23+ maxRight [n -1 ] =A [n -1 ];
24+ for (int i =1 ;i <n ; ++i ) {
25+ maxLeft [i ] =Math .max (maxLeft [i -1 ],A [i ]);
26+ maxRight [n -1 -i ] =Math .max (maxRight [n -i ],A [n -1 -i ]);
27+ }
28+
29+ int res =0 ;
30+ for (int i =1 ;i <n ; ++i ) {
31+ res +=Math .min (maxLeft [i ],maxRight [i ]) -A [i ];
32+ }
33+ return res ;
34+ }
35+ public int trap (int []A ) {
36+ int n =A .length ,res =0 ;
37+ if (n <=2 )return 0 ;
38+ int maxLeft =A [0 ];
39+ int maxRight =A [n -1 ];
40+ int left =0 ,right =n -1 ;
41+ while (left <=right ) {
42+ if (maxLeft <=maxRight ) {
43+ res +=Math .max (0 ,maxLeft -A [left ]);
44+ maxLeft =Math .max (maxLeft ,A [left ]);
45+ ++left ;
46+ }else {
47+ res +=Math .max (0 ,maxRight -A [right ]);
48+ maxRight =Math .max (maxRight ,A [right ]);
49+ --right ;
50+ }
51+ }
52+ return res ;
53+ }
54+ }
