One Line C Recursive Solution


  • 0
    H
    #define MAX(X,Y) ((X)>=(Y)?(X):(Y))
    
    int _trap(int *x, int n, int l, int r) {
        return n>0 ? MAX(l-x[0],0) + MAX(r-x[n-1],0) + _trap(x[0]<=x[n-1]?x+1:x, n-1, MAX(l,x[0]), MAX(r,x[n-1])) : 0;
    }
    
    int trap(int* height, int heightSize) {
        return _trap(height, heightSize, 0, 0);
    }
    

  • 0
    H

    Another version, more effective and easy to understand

    #define MAX(X,Y) (((X)>=(Y))?(X):(Y))
    
    int _trap(int* x, int n, int l, int r) {
        return n>0 ? l=MAX(l,x[0]), r=MAX(r,x[n-1]), l-x[0]+r-x[n-1] + _trap(l<=r?x+1:x, n-1, l, r) : 0;
    }
    
    int trap(int* height, int heightSize) {
        return _trap(height, heightSize, 0, 0);
    }
    

Log in to reply
 

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