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.

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 MarcZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcyBmb3IgY29udHJpYnV0aW5nIHRoaXMgaW1hZ2UhPC9wPgo8YnI+CjxoND6hvszi0uKhvzwvaDQ+CjxwPrj4tqhuuPa3x7i61fvK/aOstPqx7dK7uPbW+de0zbyjrMO/0ru49tb519O1xL/ttsjOqjGjrLzGy+PPwtPq1q6689b517TNvMTc17C24MnZy66jvzxicj4KPC9wPgo8cD7A/cjno7o8L3A+CjxwPlswLDEsMCwyLDEsMCwxLDMsMiwxLDIsMV0gILe1u9ggNjwvcD4KPHA+ICAgIDxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/49/1_iaglx__.png" alt="\">

上述柱状图是由数组表示[0,1,0,2,1,0,1,3,2,1,2,1]。在这种情况下，6个单位的雨水（蓝色部分）被装。

【分析】

对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是 min(leftMostHeight,rightMostHeight) - height。所以，

1. 从左往右扫描一遍，对于每个柱子，求取左边最大值；

2. 从右往左扫描一遍，对于每个柱子，求最大右值；

3. 再扫描一遍，把每个柱子的面积并累加。

也可以，

1. 扫描一遍，找到最高的柱子，这个柱子将数组分为两半；

2. 处理左边一半；

3. 处理右边一半。

【代码】

/*********************************
*   日期：2014-01-20
*   作者：SJF0115
*   题号: Trapping Rain Water
*   来源：http://oj.leetcode.com/problems/trapping-rain-water/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; class Solution { public: int trap(int A[], int n) { if(A == NULL || n < 1)return 0; int i; int* leftMostHeight = (int*)malloc(sizeof(int)*n); int* rightMostHeight = (int*)malloc(sizeof(int)*n); int maxHeight = 0; for(i = 0; i < n;i++){ leftMostHeight[i] = maxHeight; if(maxHeight < A[i]){ maxHeight = A[i]; } } maxHeight = 0; for(i = n-1;i >= 0;i--){ rightMostHeight[i] = maxHeight; if(maxHeight < A[i]){ maxHeight = A[i]; } } int water = 0; for(i =0; i < n; i++){ int curWater = min(leftMostHeight[i],rightMostHeight[i]) - A[i]; if(curWater > 0){ water += curWater; } } return water; } }; int main() { Solution solution; int result; int A[] = {0,1,0,2,1,0,1,3,2,1,2,1}; result = solution.trap(A,12); cout<
     
      
 
      
 
      
 
      
【代码2】
 
      
 
      
class Solution {
public:
    int trap(int A[], int n) {
        int *max_left = new int[n]();
        int *max_right = new int[n]();
        for (int i = 1; i < n; i++) {
            max_left[i] = max(max_left[i - 1], A[i - 1]);
            max_right[n - 1 - i] = max(max_right[n - i], A[n - i]);
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int height = min(max_left[i], max_right[i]);
            if (height > A[i]) {
                sum += height - A[i];
            }
        }
        delete[] max_left;
        delete[] max_right;
        return sum;
    }
};
      
 
      
 
      
 
      
【代码3】
 思路2 
      
 
      
class Solution {
public:
    //时间复杂度 O(n)，空间复杂度 O(1)
    int trap(int A[], int n) {
        // 最高的柱子，将数组分为两半
        int max = 0;
        for (int i = 0; i < n; i++){
            if (A[i] > A[max]) max = i;
        }
        int water = 0;
        for (int i = 0, leftMaxHeight = 0; i < max; i++){
            if (A[i] > leftMaxHeight){
                leftMaxHeight = A[i];
            }
            else {
                water += leftMaxHeight - A[i];
            }
        }
        for (int i = n - 1, rightMaxHeight = 0; i > max; i--){
            if (A[i] > rightMaxHeight){
                rightMaxHeight = A[i];
            }
            else{
                water += rightMaxHeight - A[i];
            }
        }
        return water;
    }
};
      
 
      
【代码4】
 
      

      
//第4种解法，用一个栈辅助，小于栈顶的元素压入，大于等于栈顶就把栈里所有小于或等于当
//前值的元素全部出栈处理掉。
// LeetCode, Trapping Rain Water
// 用一个栈辅助，小于栈顶的元素压入，大于等于栈顶就把栈里所有小于或
// 等于当前值的元素全部出栈处理掉，计算面积，最后把当前元素入栈
// 时间复杂度 O(n)，空间复杂度 O(n)
class Solution {
public:
    int trap(int a[], int n) {
        stack
       
        > s;
        int water = 0;
        for (int i = 0; i < n; ++i) {
            int height = 0;
            // 将栈里比当前元素矮或等高的元素全部处理掉
            while (!s.empty()) {
                int bar = s.top().first;
                int pos = s.top().second;
                // bar, height, a[i] 三者夹成的凹陷
                water += (min(bar, a[i]) - height) * (i - pos - 1);
                height = bar;
                if (a[i] < bar) // 碰到了比当前元素高的，跳出循环
                    break;
                else
                s.pop(); // 弹出栈顶，因为该元素处理完了，不再需要了
            }
            s.push(make_pair(a[i], i));
        }
        return water;
    }
};