LeetCode第240场周赛题解-一一网

第一题

var maximumPopulation = function(logs) {
    let res = 1950, maxCnt = 0
    for (let year = 1950; year <= 2050; year++) {
        let cnt = 0
        for (let log of logs) {
            if (log[0]<=year&&log[1]>year) cnt++
        }
        if (cnt > maxCnt) {
            res = year
            maxCnt = cnt
        }
    }
    return res
};
复制代码

第二题

5751. Maximum Distance Between a Pair of Values

首先想到二分法，时间复杂度 $O(nlogm)$ 。使用双指针改进后，时间复杂度降到 $O(m+n)$ 。

var maxDistance = function(nums1, nums2) {
    let i = nums1.length-1, j = nums2.length-1
    let res = 0
    while (i>=0) {
        while (j>=i&&nums2[j]<nums1[i]) j--
        res = Math.max(res, j-i)
        i--
    }
    return res
};
复制代码

第三题

5752. Maximum Subarray Min-Product

对于nums[i]，我们想知道如果nums[i]是它所在数组中的最小元素，它的结果是多少。那么我们要知道从nums[i]开始向左第一个小于它的index left[i]，以及从nums[i]开始向右第一个小于它的index right[i]，那么(left[i], right[i])表示的子数组中的最小值就是nums[i]，为了方便计算，我们先预处理求出前缀和。关于如何快速求出left[i]和right[i]，我们使用单调递增栈。具体怎么实现不多说，只提供思路，懂的都懂。这题还有一个比较麻烦的就是数值处理，因为取余的问题比赛中错了好几次，最后改成全程使用bigint才通过。

var maxSumMinProduct = function(nums) {
    const M = 1e9+7
    const n = nums.length
    let sums = [0n]
    for (let i = 0; i < n; i++) {
        sums[i+1] = sums[i]+BigInt(nums[i])
    }
    // 计算出对于每个nums[i]，左边第一个小于它的数的index，右边第一个小于它的index (使用单调增栈)
    let left = new Array(n).fill(-1), right = new Array(n).fill(n)
    let stack = [0]
    for (let i = 1; i < n; i++) {
        while (stack.length&&nums[stack[stack.length-1]]>=nums[i]) stack.pop()
        if (stack.length) left[i] = stack[stack.length-1]
        else left[i] = -1
        stack.push(i)
    }
    stack = [n-1]
    for (let i = n-2; i >= 0; i--) {
        while (stack.length&&nums[stack[stack.length-1]]>=nums[i]) stack.pop()
        if (stack.length) right[i] = stack[stack.length-1]
        else right[i] = n
        stack.push(i)
    }
    // 遍历nums中每一个元素
    let res = 0
    for (let i = 0; i < n; i++) {
        const t = BigInt(nums[i])*BigInt(sums[right[i]]-sums[left[i]+1])
        if (t>res) res = t
    }
    return res%BigInt(M)
};
复制代码

第四题

5753. Largest Color Value in a Directed Graph

首先是判断是否存在环。对于有向图判断是否存在环的方法就是利用拓扑排序，先找到入度为0的结点，然后把该结点指向的结点的入度减一，之后把该结点从图中拿掉；不断重复该过程，如果最后图中还有结点说明有环。完成这一步后就要对图进行遍历，找到所有路径计算最大颜色值。第一想法肯定是dfs，但感觉会超时；我们考虑bfs，假如对于结点i，前面所有指向它的结点都遍历过了，即当前结点i的入度已经变成0了，把前面所有指向它的结点的信息传给当前结点i。对于每个结点i，我们有一个数组，令dp[i] [j]表示对于当前结点i，以它为结尾的所有路径中颜色j出现的最多次数。

分析完了可以看出，判断是否存在环和遍历图这两步可以放在一起，即可以先遍历着，到最后遍历完了入度为0的结点后发现还有结点每遍历到就说明有环。

var largestPathValue = function(colors, edges) {
    colors = colors.split('').map(c=>c.charCodeAt()-'a'.charCodeAt())
    const n = colors.length
    // 令dp[node][color]表示以节点node为结尾的所有路径上最多有多少个颜色为color的节点
    let dp = new Array(n).fill(null).map(d=>new Array(26).fill(0))
    for (let i = 0; i < n; i++) dp[i][colors[i]] = 1
    let res = 1
    let node_linkto = new Map()
    let inDegree = new Array(n).fill(0)
    for (let [node,linkto] of edges) {
        if (node_linkto.has(node)) node_linkto.get(node).push(linkto)
        else node_linkto.set(node,[linkto])
        inDegree[linkto]++
    }
    let degree0 = []
    for (let i = 0; i < n; i++) {
        if (inDegree[i]==0) degree0.push(i)
    }
    let cntRemoved = 0
    while (degree0.length) {
        const node = degree0.pop()
        ++cntRemoved
        if (node_linkto.has(node)) {
            for (const linkto of node_linkto.get(node)) {
                for (let color = 0; color < 26; color++) {
                    dp[linkto][color] = Math.max(dp[linkto][color], dp[node][color]+(colors[linkto]==color?1:0))
                    res = Math.max(dp[linkto][color], res)
                }
                inDegree[linkto]--
                if (inDegree[linkto]==0) degree0.push(linkto)
            }
        }
    }
    return cntRemoved<n?-1:res
};
复制代码