2528. 最大化城市的最小供电站数目

[TOC]

思路

  由于我们要求的是某个值的最大值，所以我们可以采用 <二分查找> 的方式来“猜”结果。

  对于每次猜测，创建函数 $f(c)$ ，返回该数是否合法。

  我们可以采用<差分数组>的形式记录差值，差分数组相关内容参考本文补充部分。从左到右遍历，设本次猜的数为 $c$ ，遇到位置为 $i$ 处的电站小于 $c$ ，则在 $\min(i + r, n - 1)$ 处<临时>添加电站，也就是位于 $[i, \min(i + 2 * r, n - 1)]$ 的城市都增加了临时电站的覆盖。若在本次猜测中，剩余可加的电站不足，则返回 $False$，若最后剩余电站数大于等于0，则返回 $True$。

代码

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        # 差分数组
        diff = defaultdict(int)
        n = len(stations)
        for i, val in enumerate(stations):
            left = max(0, i - r)
            right = min(n, i + r + 1)
            diff[left] += val
            diff[right] -= val

        # 判断猜的数字是否合法
        def f(c):
            # 临时电站的差分数组
            td = defaultdict(int)
            # 本次猜测剩余可加电站数
            tk = k
            # 当前位置覆盖的电站数
            cnt = 0
            for i in range(n):
                # i 处的电站数
                cnt += diff[i] + td[i]
                if cnt < c:
                    # 将该位置电站数补充到 c
                    tk -= c - cnt
                    if tk < 0:
                        # 剩余可加电站不足
                        return False
                    # 补充的电站放在 min(n - 1, i * 2 * r) 处
                    td[min(n, i + 2 * r + 1)] -= c - cnt
                    # 更新该位置的电站数
                    cnt = c
            return True

        #预估上下界
        a, b = min(stations), sum(stations) + k
        # 维护左边界合法
        while a + 1 < b:
            c = a + (b - a) // 2
            if f(c):
                a = c
            else:
                b = c - 1
        if f(b):
            return b
        return a

复杂度分析

• 时间复杂度：$O(n \log D)$。每次猜测的时间复杂度为 $O(n)$，需要进行$D = sum(stations) + k - min(stations)$次猜测，总复杂度为 $O(n \log D)$.
• 空间复杂度：$O(n)$.

补充：差分数组

  给定边界 $S \geq 0$，数组 $arr$，其中 $arr[i] = [a_{i}, b_{i}],\ (0 \leq a_{i} \leq b_{i} \leq S)$，表示在 $[a_{i}, b_{i}]$ 内每个整数位置都放一个小球，返回每个坐标下的小球数量列表。

  若采用暴力方法，时间复杂度为 $O(nS)\ (n = len(arr))$。

def function(arr: list[list[int]], S: int) -> list[int]:
    ans = [0] * (S + 1)
    for a, b in arr:
        for i in range(a, b + 1):
            ans[i] += 1
    return ans

  实际上，我们只要记录每个坐标和前一个坐标的差值，即可在 $O(S)$ 的时间内计算出每个位置最后的小球数。

  创建数组 $diff$，其中 $diff[i]$ 表示 $i$ 位置和 $i - 1$位置的差值，则 $ans[i] = ans[i - 1] + diff[i]$，其中$ans[0] = 0 + diff[0]$.

  那么如何建立差分数组 $diff$ 呢？对于 $arr[i] = [a_{i}, b_{i}]$，表面含义是在 $[a_{i}, b_{i}]$ 内每个整数位置都放一个小球，我们可以从另一个角度理解：

• 位置 $a_{i}$ 相对于位置 $a_{i} - 1$来说，多增加了一个球，所以差值 $diff[a_{i}] += 1$
• 位置 $b_{i} + 1$ 相对于位置 $b_{i}$来说，少增加了一个球，所以 $diff[b_{i} + 1] -= 1$
• 对于 $[a_{i} + 1, b_{i}]$ 内的位置来说，和前一个位置一样，都增加了一个小球，所以差值没变，不需要修改差分数组 $diff$

  调整差分数组的时间复杂度为$O(n)\ (n = len(arr))$，根据差分数组求每个位置小球数的时间复杂度为 $O(S)$，则总时间复杂度为 $O(n) + O(S) = O(\min(n, S))$.

def function(arr: list[list[int]], S: int) -> list[int]:
    # 建立差分数组
    diff = defaultdict(int)
    # 调整差分数组
    for a, b in arr:
        diff[a] += 1
        diff[b] -= 1
    # 根据差分数组求各个位置的小球数
    ans = [0] * (S + 1)
    ans[i] = diff[0]
    for i in range(1, S + 1):
        ans[i] = ans[i - 1] + diff[i]
    return ans

END

  码字不易，点个赞再走呗！