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.BkJia.com/kf/ware/vc/" target="_blank" class="keylink">vcyBmb3IgY29udHJpYnV0aW5nIHRoaXMgaW1hZ2UhPC9wPgo8YnI+CjxoND6hvszi0uKhvzwvaDQ+CjxwPrj4tqhuuPa3x7i61fvK/aOstPqx7dK7uPbW+de0zbyjrMO/0ru49tb519O1xL/ttsjOqjGjrLzGy+PPwtPq1q6689b517TNvMTc17C24MnZy66jvzxicj4KPC9wPgo8cD7A/cjno7o8L3A+CjxwPlswLDEsMCwyLDEsMCwxLDMsMiwxLDIsMV0gILe1u9ggNjwvcD4KPHA+ICAgIDxpbWcgc3JjPQ=="https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012114565415.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;
    }
};