这道题做的比较艰辛，一开始自己想的是一个用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 }