SOURCE

// 链表相关 instanceof 
function myInstanceof(a, b){
    let p = a;
    while(p){
        if(p === b.prototype){
            return true;
        }
        p = p.__proto__;
    }
    return false;
}

// deep clone
function deepCopy(target){
    let result = null;
    if(typeof target === 'object'&&target){
        result = target instanceof Array?[]:{};
        for(let i in target){
            result[i] = deepCopy(target[i]);
        }
    }else{
        result = target;
    }
    return result;
}

// leetcode 42 stack 接雨水
let arr = [0, 1, 5, 1, 4, 2, 3]
function trap(heights){
    let sum = 0;
    for(let i = 1; i < heights.length - 1; i++){
        let leftMax = 0;
        for(let l = i - 1; l >= 0; l--){
            leftMax = (heights[l] >= leftMax) ? heights[l] : leftMax;
        }
        let rightMax = 0;
        for(let r = i + 1; r < heights.length; r++){
            rightMax = (heights[r] >= rightMax) ? heights[r] : rightMax;
        }
        let min = Math.min(leftMax, rightMax);
        if(min > heights[i]){
            sum = sum + min - heights[i];
        }
    }
    return sum;
}
console.log(trap(arr));

//leetcode 42 使用指针遍历
function trap2(heights){
    let len = heights.length;
    let sum = 0;
    let left = 0;
    let right = len - 1;
    let lMax = heights[0];
    let rMax = heights[len - 1];

    while(left <= right){
        lMax = Math.max(lMax, heights[left]);
        rMax = Math.max(rMax, heights[right]);
        if(lMax < heights[right]){
            sum += lMax - heights[left];
            left++;
        }else{
            sum += rMax - heights[right];
            right--;
        }
    }
}
console.log(trap2(arr));