微信校招面经

// 直接暴力会报超时，仅作参考
var maxProfit = function(prices) {
    let max = 0
    for(let i=0; i<prices.length; i++) {
        const cur = prices[i]
        for(let j=i; j<prices.length; j++) {
            if(prices[j] > cur) {
                max = Math.max(max, prices[j] - cur)
            }
        }
    }
    return max
};

// 遍历的时候记录左侧的最小值
// 时间复杂度O(n) 空间复杂度O(1)

var maxProfit = function(prices) {
    let low = Number.MAX_SAFE_INTEGER
    let ans = 0
    for(let i=0; i<prices.length; i++) {
        low = Math.min(low, prices[i])
        ans = Math.max(ans, prices[i] - low)
    }
    return ans
}

// 效率很低，js只能击败5%
// 以当前墙为分界，分别找出左右数组的最高墙
// 时间复杂度O(n^2) 空间复杂度O(1)

var trap = function(height) {
    let sum = 0
    for(let i=1; i<height.length - 1; i++) {
        const maxLeft = Math.max(...height.slice(0, i))
        const maxRight = Math.max(...height.slice(i+1))
        const min = Math.min(maxLeft, maxRight)
        if(min > height[i]) {
            sum += min - height[i]
        }
    }

    return sum
};

// 上一个解法，对于每一列，都要求左边和右边的最高墙，都是要重新遍历
// 分别定义max_left[] 和 max_right[] 数组，分别表示第i列时左边最高墙和右边最高墙
// 这个效率高点，击败js 62%
// 时间复杂度O(n)
// 空间复杂度O(n)

var trap = function(height) {
    let sum = 0
    const len = height.length
    const maxLeftArr = new Array(len).fill(0)
    const maxRightArr = new Array(len).fill(0)

    for(let i=1; i<len-1; i++) {
        maxLeftArr[i] = Math.max(maxLeftArr[i-1], height[i-1])
    }
    for(let i=len-2; i>=0; i--) {
        maxRightArr[i] = Math.max(maxRightArr[i+1], height[i+1])
    }
    for(let i=1; i<len-1; i++) {
        const min = Math.min(maxLeftArr[i], maxRightArr[i])
        if(min > height[i]) {
            sum += min - height[i]
        }
    }
    return sum
};