42. 接雨水C

因为还是双指针的题目。

我想到的短板效应,看两头，能接住的水也就是取决于最短的一方。

每次看两头后，在里面找比最短还短的地方，那个就是有水的地方。找到水后在把它填平，防止重复找到。然后两头往中间靠就行了。

int min(int i,int j){
        if(i>j) return j;
        return i;
    }

int findsum(int* height,int head,int tail,int t){
    if(t==0) return 0;
    int sum=0;
    for(;head<=tail;head++){
        if(height[head]<t){
            sum+=t-height[head];
            height[head]=t;
        }
    }
    return sum;
}

int trap(int* height, int heightSize) {
    int head=0,tail=heightSize-1;
    while(height[head]==0 && head<tail) head++;
    while(height[tail]==0 && tail>head) tail--;
    int sum=0;
    while(head <tail){
        int t=min(height[head],height[tail]);
        sum+=findsum(height,head+1,tail-1,t);
        if(height[head]==height[tail]){
            head++;
            tail--;
            while(head<tail && height[head]<=height[head-1]) head++;
            while(head<tail && height[tail]<=height[tail+1]) tail--;
        }else if(height[head] <height[tail]){
            head++;
             while(head<tail && height[head]<=height[head-1]) head++;
        }else{
            tail--;
            while(head<tail && height[tail]<=height[tail+1]) tail--;
        }
    }
    return sum;
}

结果：懒得优化了。等考上研究生了。在提高要求把。目前还是把题目能解出来的阶段。