2026-09-22：照亮道路的最少灯泡数。用go语言，有一条长度为 n 的道路，位置编号从 0 到 n-1，并用数组 lights 表示初始照明情况。如果|lights|复杂度|差分|灯泡

2026-09-22：照亮道路的最少灯泡数。用go语言，有一条长度为 n 的道路，位置编号从 0 到 n-1，并用数组 lights 表示初始照明情况。

如果 lights[i] 是一个大于 0 的数 v，说明位置 i 上有一盏可用灯，它能照到从 i 向左 v 个位置、向右 v 个位置的范围，也就是 i-v 到 i+v。若这个范围超出道路边界，就只计算道路内的部分。若 lights[i] 等于 0，说明位置 i 没有可用灯。

只要某个位置落在至少一盏可用灯的照明范围内，就认为这个位置已经可见。

你还可以在道路上的任意位置新增灯。每新增一盏灯放在位置 j，它可以照到 j 本身以及左右相邻的位置，也就是 j-1 到 j+1；超出道路边界时同样只保留道路内的部分。

现在要求让 0 到 n-1 的所有位置都可见，问最少需要新增多少盏灯。

1 <= n == lights.length <= 100000。

0 <= lights[i] <= n。

输入： lights = [0,0,0,2,0]。

输出： 1。

解释：

因为 lights[3] = 2，所以位置 3 正常工作的灯泡照亮了位置 [1, 2, 3, 4]。

在位置 1 安装一个额外的灯泡照亮了位置 [0, 1, 2]，使每个位置都可见。

因此，所需的最少额外灯泡数量为 1。

题目来自力扣3964。

详细过程如下：

第一步，确定道路长度 n，并准备一个长度为 n+1 的差分数组。这个差分数组不直接记录每个位置被多少灯照亮，而是记录“覆盖数量”的变化量。后续从左到右做前缀和，就能知道每个位置当前被多少盏灯覆盖。

第二步，遍历初始的 lights 数组。对于每个位置 i：
如果 lights[i] 等于 0，说明这个位置没有正常工作的灯，不需要处理。
如果 lights[i] 是一个大于 0 的数 v，说明位置 i 有一盏灯，它能照亮从 i-v 到 i+v 的范围。但道路边界是 0 到 n-1，所以实际照亮范围是：
左边界为 max(0, i-v)，
右边界为 min(n-1, i+v)。

在差分数组中，对这个照亮区间整体加 1。具体表现为：在左边界位置加 1，在右边界后面一个位置减 1。因为右边界最大是 n-1，所以右边界后一个位置可能到 n，因此差分数组长度设为 n+1。这样处理完所有初始灯后，差分数组就记录了初始灯在每个位置造成的覆盖变化。

第三步，初始化答案为 0，初始化当前覆盖计数为 0。然后从位置 0 开始，一直到位置 n-1，依次扫描每个位置。

第四步，对于当前扫描到的位置 i，先把差分数组在 i 处的变化量累加到当前覆盖计数中。这个覆盖计数表示位置 i 当前被多少盏灯照亮，包括原本就有的灯和之前新增的灯。

第五步，判断当前位置 i 是否已经被照亮。如果覆盖计数大于 0，说明位置 i 已经可见，不需要新增灯，继续扫描下一个位置。

第六步，如果覆盖计数等于 0，说明位置 i 没有任何灯能照到，必须新增至少一盏灯。为了让新增灯发挥最大作用，贪心地把灯安装在位置 i+1。原因是：一盏新增灯安装在位置 j 时，能照亮 j-1、j、j+1。如果要覆盖当前位置 i，那么新增灯可以放在 i-1、i、i+1 这些位置。其中放在 i+1 是最靠右的选择，它仍然能覆盖 i，同时还能尽量向右覆盖 i+1 和 i+2。这样对后面的位置最有利，因此不会比放在其他位置差。

第七步，新增这盏灯后，答案数量加 1。因为当前位置 i 已经被这盏新增灯覆盖，所以当前覆盖计数也要加 1。同时，这盏新增灯照亮的是 i、i+1、i+2，因此从位置 i+3 开始，它就不再提供照明。于是需要在差分数组中，在 min(i+3, n) 的位置减 1，表示从那里开始覆盖数量减少 1。如果 i+3 已经超过 n-1，就记在 n 处，不影响后续扫描。

第八步，继续向右扫描，重复上述过程，直到所有位置都检查完。最终答案变量中记录的就是最少需要新增的灯泡数量。

以输入 lights = [0,0,0,2,0] 为例：
道路长度 n=5。
位置 3 有一盏灯，值 v=2，所以它照亮 max(0,3-2)=1 到 min(4,3+2)=4，也就是位置 1、2、3、4。
扫描位置 0 时，覆盖计数为 0，说明位置 0 没被照亮。于是新增一盏灯放在位置 1，它照亮位置 0、1、2。答案变为 1。
之后位置 1、2 被新增灯照亮，位置 3、4 被原本位置 3 的灯照亮，所有位置都可见。
因此最少新增灯数为 1。

这个贪心策略的正确性在于：每次遇到一个没被照亮的位置 i，任何合法方案都必须至少新增一盏灯来覆盖它。把灯放在 i+1 既能覆盖 i，又能尽可能向右延伸，不会减少对左侧已经处理过的位置的影响，也不会比放在更左的位置更差。因此这样贪心可以得到最少新增灯数。

时间复杂度：需要遍历一次 lights 数组来构建差分数组，再从左到右扫描一次道路位置，两次都是线性操作，所以总时间复杂度是 O(n)。

额外空间复杂度：主要使用了一个长度为 n+1 的差分数组，因此总额外空间复杂度是 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

func minLights(lights []int) (ans int) {
    n := len(lights)
    diff := make([]int, n+1)
    for i, v := range lights {
        if v > 0 {
            // 照亮 [max(i-v, 0), min(i+v, n-1)]
            diff[max(i-v, 0)]++
            diff[min(i+v+1, n)]--
        }
    }

sumD := 0
    for i, d := range diff[:n] {
        sumD += d
        if sumD == 0 {
            // 在 i+1 装一个灯泡，照亮 [i, i+2]
            ans++
            sumD++ // diff[i]++ 直接更新到 sumD 中
            diff[min(i+3, n)]--
        }
    }
    return
}

func main() {
    lights := []int{0, 0, 0, 2, 0}
    result := minLights(lights)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minLights(lights):
    n = len(lights)
    diff = [0] * (n + 1)

# 先处理原本就存在的灯泡照明范围
    for i, v in enumerate(lights):
        if v > 0:
            left = max(i - v, 0)
            right = min(i + v + 1, n)
            diff[left] += 1
            diff[right] -= 1

ans = 0
    cover = 0

# 从左到右扫描，若当前位置没有被照亮，则新增一盏灯
    for i in range(n):
        cover += diff[i]

if cover == 0:
            ans += 1
            cover += 1
            # 新增灯放在 i + 1，可以照亮 i、i + 1、i + 2
            # 因此从 i + 3 开始不再受这盏新增灯影响
            diff[min(i + 3, n)] -= 1

return ans

if __name__ == "__main__":
    lights = [0, 0, 0, 2, 0]
    result = minLights(lights)
    print(result)

C++完整代码如下：

  

  

  


int minLights(const std::vector& lights) {
    int n = lights.size();
    std::vector diff(n + 1, 0);

// 处理原本就存在的灯泡
    for (int i = 0; i < n; ++i) {
        int v = lights[i];
        if (v > 0) {
            int left = std::max(i - v, 0);
            int right = std::min(i + v + 1, n);
            diff[left]++;
            diff[right]--;
        }
    }

int ans = 0;
    int sumD = 0;

// 从左到右扫描，若当前位置没有被照亮，则新增一盏灯
    for (int i = 0; i < n; ++i) {
        sumD += diff[i];

if (sumD == 0) {
            ans++;
            sumD++;
            // 新增灯放在 i + 1，可以照亮 i、i + 1、i + 2
            // 因此从 i + 3 开始不再受这盏新增灯影响
            diff[std::min(i + 3, n)]--;
        }
    }

return ans;
}

int main() {
    std::vector lights = {0, 0, 0, 2, 0};
    int result = minLights(lights);
    std::cout << result << std::endl;
    return0;
}