題目

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
.

分析

思路是首先求得每個位置的水面高度，再由其求得水的體積。
而求水面高度，則可分為兩種情況：

• 當(dāng)前位置后有大于等于當(dāng)前高度的位置，則自該位置起，將水面高度賦為當(dāng)前高度
• 當(dāng)前位置后沒有大于等于當(dāng)前高度的位置了，則自該位置之后，將水面高度賦為其之后的最高高度。

由于這兩種情況都需要用到其后的最大高度，所以可以使用一個數(shù)組保存該值。另外別忘了每個位置的水面高度不能低于該位置的高度。

實現(xiàn)

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=1) return 0;
        int n = height.size();
        int maxheight[n] = {0};
        int maxpos[n] = {0};
        int water[n] = {0};
        maxheight[n-1] = height[n-1];
        maxpos[n-1] = n-1;
        for(int i=n-2; i>=0; i--){
            if(height[i] >= maxheight[i+1]){
                maxheight[i] = height[i];
                maxpos[i] = i;
            }
            else{
                maxheight[i] = maxheight[i+1];
                maxpos[i] =maxpos[i+1];
            }
        }
        int i=0;
        while(i<n-1){
            if(height[i]>=maxheight[i+1]){
                water[i] = height[i];
                for(int j=i+1; j<=maxpos[i+1]; j++){
                    water[j] = maxheight[i+1];
                }
                i = maxpos[i+1];
            }
            else{
                int tmp = height[i];
                while(i<n && height[i]<=tmp){
                    water[i] = tmp;
                    i++;
                }
                water[i] = height[i];
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            ans += water[i] - height[i];
        }
        return ans;
    }
};

思考

看了題解發(fā)現(xiàn)有更簡單的思路：

• 掃描一遍， 找到最高的柱子，該柱子將數(shù)組分成左右兩組
• 對于兩組分別處理

參考代碼

class Solution{
  public:
    int trap(const vector<int> &A){
        const int n = A.size();
        int max = 0; //最高的柱子，將數(shù)組分成兩半
        for (int i = 0; i < n; i++)
            if (A[i] > A[max])
                max = i;
        int water = 0;
        for (int i = 0, peak = 0; i < max; i++)
            if (A[i] > peak)
                peak = A[i];
            else
                water += peak - A[i];
        for (int i = n - 1, top = 0; i > max; i--)
            if (A[i] > top)
                top = A[i];
            else
                water += top - A[i];
        return water;
    }
};