Leetcode: Trapping Rain Water

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

这道题做的比较艰辛，一开始自己想的是一个用stack的解法，感觉过于繁琐（出栈，入栈，计算容积），但未尝不是一个好的尝试，这个方法还是有点小问题，过后会好好想清楚。看了网上提示完成了最终的方法，这个方法两次遍历数组，第一次遍历找每个元素右边最大的元素，第二次遍历寻找每个元素左边最大的元素，同时计算该index可以存放的水容积： min{lefthighest, righthighest}-A[i]

最终方法：

 1 public class Solution {
 2     public int trap(int[] A) {
 3         int length = A.length, sum = 0, min = 0;
 4         int[] lefthighest = new int[length];
 5         int[] righthighest = new int[length];
 6         
 7         for (int i=length-1; i>=0; i--) {
 8             if (i == length-1) {
 9                 righthighest[i] = 0;
10             }
11             else if (A[i+1] > righthighest[i+1]) {
12                 righthighest[i] = A[i+1];
13             }
14             else if (A[i+1] <= righthighest[i+1]) {
15                 righthighest[i] = righthighest[i+1];
16             }
17         }
18         
19         for (int j=0; j<length; j++) {
20             if (j==0) {
21                 lefthighest[j] = 0;
22             }
23             else if (A[j-1] > lefthighest[j-1]) {
24                 lefthighest[j] = A[j-1];
25             }
26             else if (A[j-1] <= lefthighest[j-1]) {
27                 lefthighest[j] = lefthighest[j-1];
28             }
29             min = Math.min(lefthighest[j], righthighest[j]);
30             if (min > A[j]) { //can store water
31                 sum += min - A[j];
32             }
33         }
34         return sum;
35     }
36 }

之前用stack尝试解的方法，较复杂，但是是个不错的思考切入点：

 1 public class Solution {
 2     public int trap(int[] A) {
 3         Stack<Integer> s = new Stack<Integer>();
 4         int i = 0, sum = 0, lastpop = 0;
 5         while (i < A.length){
 6             if (s.empty()) {
 7                 s.push(i);
 8                 i++;
 9                 continue;
10             }
11             if (A[s.peek()] < A[i]){ //can hold water if stack contains other elements
12                 while (A[s.peek()] < A[i]){
13                     lastpop = A[s.pop()];
14                     if (s.empty()){
15                         s.push(i);
16                         i++;
17                         continue;
18                     }
19                     sum += (i - s.peek() -1) * (A[s.peek()] - lastpop);
20                 }
21                 if (A[s.peek()] > A[i]){
22                     sum += (i - s.peek() -1) * (A[i] - lastpop);
23                     s.push(i);
24                     i++;
25                     continue;
26                 }
27                 if (A[s.peek()] == A[i]){
28                     sum += (i - s.peek() -1) * (A[i] - lastpop);
29                     s.pop();
30                     i++;
31                     continue;
32                 }
33             }
34             else if (s.peek() == A[i]){
35                 i++;
36                 continue;
37             }
38             else if (s.peek() > A[i]){
39                 s.push(i);
40                 i++;
41                 continue;
42             }
43         }
44         return sum;
45     }
46 }