第 240 场周赛题解

Q1 1854. 人口最多的年份 (opens new window)

该题若是没有给出范围 or 范围较大，则需要使用差分数组来处理。而真正给出的范围较小，因此直接暴力即可。

class Solution1854 {
    fun maximumPopulation(logs: Array<IntArray>): Int {
        var max = 0
        var ans = -1
        for (i in 1950..2050) {
            val cnt = logs.count { it[0] <= i && it[1] - 1 >= i }
            if (cnt > max) {
                max = cnt
                ans = i
            }
        }
        return ans
    }
}

Q2 1855. 下标对中的最大距离 (opens new window)

简单的双指针操作，时间复杂度为$O(n + m)$。

class Solution1855 {
    fun maxDistance(nums1: IntArray, nums2: IntArray): Int {
        var ans = 0
        var i = 0
        var j = 0
        while (i in nums1.indices && j in nums2.indices) {
            j = maxOf(j, i)
            while (j in nums2.indices && nums2[j] >= nums1[i]) {
                ans = maxOf(ans, j - i)
                j++
            }
            i++
        }
        return ans
    }
}

Q3 1856. 子数组最小乘积的最大值 (opens new window)

比赛时没做出来，还要加强学习！

可以以每个元素为最小值，向左向右查到最远距离。这个查找如果用暴力，时间复杂度为$O(n^2)$，会超时。可以使用两个单调栈分别求出左侧、右侧的下标，将时间复杂度降低为$O(n)$。

class Solution5752 {
    fun maxSumMinProduct(nums: IntArray): Int {
        val mod = 1000000007L
        val preSum = LongArray(nums.size + 1)
        for (i in nums.indices) {
            preSum[i + 1] = preSum[i] + nums[i]
        }
        val rightSmall = IntArray(nums.size) { nums.size }
        val leftSmall = IntArray(nums.size) { -1 }
        val stack = Stack<Int>()
        for (i in nums.indices) {
            while (stack.isNotEmpty() && nums[i] < nums[stack.peek()]) {
                rightSmall[stack.pop()] = i
            }
            stack.push(i)
        }
        stack.clear()
        for (i in nums.indices.reversed()) {
            while (stack.isNotEmpty() && nums[i] < nums[stack.peek()]) {
                leftSmall[stack.pop()] = i
            }
            stack.push(i)
        }
        var ans = 0L
        for (i in nums.indices) {
            val left = leftSmall[i]
            val right = rightSmall[i]
            ans = maxOf(ans, nums[i] * (preSum[right] - preSum[left + 1]))
        }
        return (ans % mod).toInt()
    }
}

Q4 1857. 有向图中最大颜色值 (opens new window)

比赛时，写完了图的拓扑排序，之后使用正向查找，会超时...

需要使用$DP$进行逆向查找，并且每次查找$a..z$中的一个，降低了时间复杂度，为$O(M * 26)$。

class Solution1857 {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        val n = colors.length
        val g = Graph(n)
        edges.forEach {
            g.addEdgeOri(it[0], it[1])
        }
        val arr = g.topologicalSort()
        if (arr.isEmpty()) return -1
        arr.reverse()
        var ans = 0
        for (i in 'a'..'z') {
            val dp = IntArray(n)
            for (j in arr.indices) {
                for (k in g.adj[arr[j]]) {
                    dp[arr[j]] = maxOf(dp[arr[j]], dp[k])
                }
                dp[arr[j]] += if (colors[arr[j]] == i) 1 else 0
                ans = maxOf(ans, dp[arr[j]])
            }
        }
        return ans
    }
}

class Graph(val n: Int) {

    // 图中边（可以有方向）
    var adj: Array<LinkedList<Int>> = Array(n) { LinkedList<Int>() }

    // 图中边的权重（可以有方向）
    val weight = HashMap<Int, HashMap<Int, Int>>()

    init {
        for (i in 0 until n) {
            weight[i] = hashMapOf()
        }
    }

    fun addEdgeOri(i: Int, j: Int, w: Int = 0) {
        adj[i].add(j)
        weight[i]!![j] = w
    }

    fun addEdge(i: Int, j: Int, w: Int = 0) {
        // Add w to v's list.
        adj[i].add(j)
        // Add v to w's list
        adj[j].add(i)
        weight[i]!![j] = w
        weight[j]!![i] = w
    }
}

// prints a Topological Sort of the complete graph
fun Graph.topologicalSort(): ArrayList<Int> {
    // Create a array to store indegrees of all
    // vertices. Initialize all indegrees as 0.
    val indegree = IntArray(n)

    // Traverse adjacency lists to fill indegrees of
    // vertices. This step takes O(V+E) time
    for (i in 0 until n) {
        val temp = adj[i]
        for (node in temp) {
            indegree[node]++
        }
    }

    // Create a queue and enqueue all vertices with
    // indegree 0
    val q: Queue<Int> = PriorityQueue<Int>() { a, b ->
        indegree[b] - indegree[a]
    }
    for (i in 0 until n) {
        if (indegree[i] == 0)
            q.add(i)
    }

    // Initialize count of visited vertices
    var cnt = 0

    // Create a vector to store result (A topological
    // ordering of the vertices)
    val topOrder = ArrayList<Int>()
    while (!q.isEmpty()) {
        // Extract front of queue (or perform dequeue)
        // and add it to topological order
        val u = q.poll()
        topOrder.add(u)

        // Iterate through all its neighbouring nodes
        // of dequeued node u and decrease their in-degree
        // by 1
        for (node in adj[u]) {
            // If in-degree becomes zero, add it to queue
            if (--indegree[node] == 0)
                q.add(node)
        }
        cnt++
    }

    // Check if there was a cycle
    if (cnt != n) {
        println("There exists a cycle in the graph")
        return arrayListOf()
    }

    val ans = arrayListOf<Int>()
    // Print topological order
    for (i in topOrder) {
        ans.add(i)
    }
    return ans
}