🔗 🟡 3964. Minimum Lights to Illuminate a Road

Problem Statement

題目簡述

給定一個長度為 $n$ 的陣列 lights，代表道路上位置 $0$ 到 $n-1$ 的初始燈泡狀態：

若 lights[i] = v > 0，表示位置 $i$ 有一個工作的燈泡，可以照亮 $[i - v, i + v]$ 範圍內的所有位置。
若 lights[i] = 0，表示該位置沒有工作燈泡。

我們可以安裝額外的燈泡，每個額外燈泡安裝在位置 $j$ 可以照亮 $[j - 1, j + 1]$ 範圍內的所有位置。

求最少需要安裝多少個額外燈泡，才能使整條道路的每個位置都被照亮。

Constraints

約束條件

$1 \le n == \text{lights.length} \le 10^5$
$0 \le \text{lights}[i] \le n$

思路：差分陣列 + 貪心

1. 題型定位：區間覆蓋

本題本質是區間覆蓋問題：給定一些初始區間（工作燈泡的覆蓋範圍），求最少需要添加多少個固定長度的新區間（半徑為 $1$ 的額外燈泡），才能完整覆蓋整條線段。

題型總結

差分陣列維護區間覆蓋狀態 + 從左到右遇缺即補的貪心模型，在路燈安置、灌溉覆蓋、基地台選址等場景反覆出現，是區間覆蓋類問題的核心套路。

2. 從暴力出發：為什麼需要差分陣列？

最直接的想法：對於每個初始燈泡，遍歷其覆蓋區間內的所有位置並標記為「已照亮」。但每個燈泡的覆蓋半徑可能高達 $n$ ，總複雜度 $\mathcal{O}(n^2)$ ，在 $n = 10^5$ 下顯然不可行。

標記「哪些位置被照亮」本質上是在做「區間加值」。有沒有比逐個位置修改更快的方法？

答案是差分陣列：對 $[l, r]$ 區間加 $1$ ，只需在 $l$ 處 $+1$ 、 $r+1$ 處 $-1$ ，最後一次前綴和掃描即可還原每個位置的實際值。

前置知識：差分陣列

差分陣列是維護「區間修改、單點查詢」的經典工具。
對於區間 $[l, r]$ 的加 $1$ 操作，只需要在差分陣列中令 $l$ 位置 $+1$ 且 $r+1$ 位置 $-1$ 。
最後對差分陣列求前綴和，即可在 $\mathcal{O}(n)$ 時間內得到每個位置的最終值。

初始化時，對每個工作燈泡，將其覆蓋區間用差分陣列標記 $+1$ ，然後做一次前綴和還原，就能知道每個位置被初始燈泡覆蓋了幾次。

3. 貪心決策：遇缺即補，燈泡靠右放

現在有了每個位置的覆蓋次數，從左到右掃描：

若當前位置已被覆蓋（次數 $> 0$ ）：繼續前進。
若當前位置未被覆蓋（次數 $= 0$ ）：必須放置一個額外燈泡。

關鍵觀察：燈泡放哪最優？

額外燈泡的半徑為 $1$ ，要覆蓋當前未被照亮的位置，燈泡可以放在 $[i-1, i+1]$ 中的任何位置。但為了最大化對後續位置的貢獻，應該放在最右側，即 $i+1$ ，這樣它的覆蓋區間是 $[i, i+2]$ ，能順便照亮後續兩個位置。

在差分陣列上的操作體現為：放置新燈泡後，將當前位置的覆蓋次數加 $1$ ，並在該燈泡覆蓋結束的下一個位置（即 $\min(i+2, n-1) + 1$ ）處減 $1$ ，表示它的覆蓋到此結束。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，初始化差分陣列與一次線性掃描各 $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(n)$ ，差分陣列需要 $n+1$ 的輔助空間

Code

class Solution:
    def minLights(self, lights: list[int]) -> int:
        n = len(lights)
        diff = [0] * (n + 1)  # 差分陣列
        for i, v in enumerate(lights):
            if v > 0:
                diff[max(i - v, 0)] += 1
                diff[min(i + v, n - 1) + 1] -= 1

        ans = s = 0
        for i in range(n):
            s += diff[i]
            if s == 0:  # 需要額外放置燈，放置在 i + 1 可以覆蓋 [i, i + 2]
                s += 1
                ans += 1
                diff[min(i + 2, n - 1) + 1] -= 1
        return ans