c easy O(n) solution


  • 0
    C

    '''int min(int a,int b){
    return a>b?b:a;
    }

    int trap(int* height, int heightSize) {
    int *left_max,right_max;
    left_max=(int
    )malloc(sizeof(int)heightSize);
    right_max=(int
    )malloc(sizeof(int)*heightSize);
    int max1=0,max2=0;
    for(int i=0;i<heightSize;i++){
    left_max[i]=max1;
    if(height[i]>max1)
    max1=height[i];
    right_max[heightSize-1-i]=max2;
    if(height[heightSize-1-i]>max2)
    max2=height[heightSize-1-i];
    }
    int sum=0;
    for(int i=0;i<heightSize;i++){
    if(height[i]>min(left_max[i],right_max[i])) continue;
    sum+=(min(left_max[i],right_max[i])-height[i]);
    }
    return sum;
    } '''


  • 0
    V

    Nice! But, please free the memory before returning. :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.