接雨水

接雨水问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int i = 0, j = height.size()-1;
        res += (j-i-2) * min(height[i],height[j]);
        while(i<j){
            if(height[i]<=height[j]){
                i++;
                res -= height[i];
                if(height[i]>min(height[i-1],height[j]))
                    res += (j-i-2) * abs(height[i]-height[j]);
            }else if(height[i]>height[j]){
                j--;
                res -= height[j];
                if(height[j]>min(height[i],height[j+1]))
                    res += (j-i-2) * abs(height[i]-height[j]);
            }
        }
        return res;
    }
};

这个做法是不正确的

下面给出正确的思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        int l[size];
        int r[size];
        int max_l = -1,max_r = -1;
        for(int i = 0;i<size;i++){
            l[i] = max_l;
            max_l = max(height[i],max_l);
        }
        for(int i = size-1;i>=0;i--){
            r[i] = max_r;
            max_r = max(height[i],max_r);
        }
        int res = 0;
        for(int i = 1;i<size-1;i++){
            int t = min(l[i],r[i]) - height[i];
            res += t>=0?t:0;
        }
        // for(int x:r){
        //     printf("%d ",x);
        // }
        // cout << endl;
        // for(int x:l){
        //     printf("%d ",x);
        // }
        // cout << endl;
        return res;
    }
};