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. Thanks Marcos for contributing this image!
方法一：
时间复杂度 O(n)，空间复杂度 O(n)
对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是 min(leftMostHeight,rightMostHeight) - height。所以，
1. 从左往右扫描一遍，对于每个柱子，求取左边最大值；
2. 从右往左扫描一遍，对于每个柱子，求最大右值；
3. 再扫描一遍，把每个柱子的面积并累加。
code：
1 class Solution { 2 public: 3 int trap(int A[], int n) 4 { 5 vector left; 6 vector right; 7 left.resize(n); 8 right.resize(n); 9 10 //printArray(A, n);11 12 left[0] == 0;13 right[n-1] == 0;14 15 // get the left's max 16 for(int i = 1; i< n;i++)17 {18 left[i] = max(left[i-1], A[i-1]);19 }20 //printVector(left);21 22 // get the right's max 23 for(int i = n-2; i>=0;i--)24 {25 right[i] = max(right[i+1], A[i+1]);26 }27 //printVector(right);28 29 // clac the trap water30 int sum =0;31 int height = 0;32 for(int i = 0; i< n;i++)33 {34 height = min(left[i], right[i]);35 if(height > A[i])36 sum += height - A[i];37 }38 return sum;39 }40 }; 方法二：
时间复杂度 O(n)，空间复杂度 O(1)
1. 扫描一遍，找到最高的柱子，这个柱子将数组分为两半；
2. 处理左边一半；
3. 处理右边一半。
1 class Solution { 2 public: 3 int trap(int A[], int n) { 4 int max = 0; 5 for(int i = 0; i < n; i++) 6 if (A[i] > A[max]) max = i; 7 int water = 0; 8 int left_max_height = 0; 9 // calc the left_max_height, at the same time update water10 for (int i = 0; i < max; i++)11 if (A[i] > left_max_height) 12 left_max_height = A[i];13 else 14 water += left_max_height - A[i];15 int right_max_height = 0;16 // calc the right_max_height, at the same time update water17 for (int i = n - 1; i > max; i--)18 if (A[i] > right_max_height) 19 right_max_height = A[i];20 else 21 water += right_max_height - A[i];22 return water;23 } 24 };
方法3：
// LeetCode, Trapping Rain Water // 用一个栈辅助，小于栈顶的元素压入，大于等于栈顶就把栈里所有小于或 // 等于当前值的元素全部出栈处理掉，计算面积，最后把当前元素入栈 // 时间复杂度 O(n)，空间复杂度 O(n) 可以用std::pair 代替 struct Node结构
1 struct Node 2 { 3 int val; 4 int index; 5 Node(){} 6 Node(int v, int idx):val(v), index(idx){} 7 }; 8 9 class Solution {10 public:11 int trap(int A[], int n) {12 stack s;13 int sum = 0;14 for(int i = 0; i < n; i++)15 {16 int height = 0;17 // 将栈里比当前元素矮或等高的元素全部处理掉18 while(!s.empty())19 {20 Node node = s.top();21 // 碰到了比当前元素高的，先计算面积，如{4,3，2}，再跳出while循环, 将当前元素压栈22 if (A[i] < node.val ) // A[] = {4, 2,3}, calc sum23 {24 int width = i - node.index - 1;25 sum += A[i] * width - height * width;26 break;27 }28 else29 {30 // node.val, height, a[i] 三者夹成的凹陷31 int width = i - node.index - 1;32 sum += node.val * width - height * width;33 height = node.val;// update height34 // 弹出栈顶，因为该元素处理完了，不再需要了35 s.pop();36 }37 }38 // 所有元素都要入栈39 s.push(Node(A[i], i));40 }41 42 return sum;43 }44 };