🔗 🟡 Zero Array Transformation II

Problem Statement

題目簡述

給定整數陣列 nums 與 mm 組查詢，每組查詢 [l,r,v][l, r, v] 表示可以將區間 [l,r][l, r] 內每個元素各自最多減少 vv。查詢必須按順序使用（使用前綴），求最少需要多少組查詢才能使整個陣列全部 ≤0\le 0。若無法達成則返回 −1-1。

約束條件

  • 1<=nums.length<=1051 <= \text{nums.length} <= 10^5
  • 0<=nums[i]<=5×1050 <= \text{nums}[i] <= 5 \times 10^5
  • 1<=queries.length<=1051 <= \text{queries.length} <= 10^5
  • queries[i].length==3\text{queries}[i].\text{length} == 3
  • 0<=li<=ri<nums.length0 <= l_i <= r_i < \text{nums.length}
  • 1<=vi<=51 <= v_i <= 5

思路

問題等價轉換

題面最容易卡住的一點：查詢 [l,r,v][l,r,v] 不是要求區間內每個數都減同一個值，而是每個位置各自最多可以減 vv，各位置互不影響。

等價命題

題目等價於：找最小的 kk，使得對所有位置 ii，前 kk 個查詢中覆蓋位置 ii 的所有減少額度之和都 ≥\ge 該位置的初始值。

即：設固定一個 kk，只考慮前 kk 組查詢，需要判定

∀i,∑0≤j<klj≤i≤rjvj≥nums[i]\forall i, \quad \sum_{\substack{0\le j<k \\ l_j\le i\le r_j}} v_j \ge \text{nums}[i]

前置知識：差分陣列

若經常對區間做同加同減，差分陣列可以把區間操作變成兩個端點操作：在左端點加上變化量，右端點加一處減去變化量。最後從左到右累加，得到每個位置的實際值。這是處理區間增減的最高效手段，也是本題判定「前 kk 組查詢是否足夠」的核心工具。

方法一：二分答案 + 差分陣列

看到「最小查詢數」，可以先思考答案是否具有單調性，如果滿足單調性，則可以用二分答案來解決。

當前 kk 組查詢可以滿足條件時，k+1,k+2,…,mk+1, k+2, \dots, m 組查詢也必然可以滿足條件；當前 kk 組查詢無法滿足條件時，1,2,…,k−11, 2, \dots, k-1 組查詢也必然無法滿足條件。因此答案具有單調性。

接著考慮如何寫二分的檢查函數 check(k)：先只取前 kk 組查詢，判斷每個位置累積的總減少額度是否都 ≥\ge 該位置的初始值。直接對每個位置枚舉每組查詢是 O(nk)O(nk)，顯然是不能接受的，但由於每組查詢都給一段區間都加上同一個值，因此可以使用差分陣列將區間操作轉換為兩個端點的操作，最後再前綴和掃一次即可。

複雜度分析

  • 時間複雜度：O((n+m)log⁡m)\mathcal{O}((n + m)\log m) —— 每次判定 O(n+m)\mathcal{O}(n+m)，二分 O(log⁡m)\mathcal{O}(\log m) 次
  • 空間複雜度：O(n)\mathcal{O}(n) —— 差分陣列

方法二：雙指標單調性優化

二分答案每次都重建差分陣列，重複掃了已處理過的查詢。瓶頸在於：相鄰兩次判定的差分狀態高度重疊（前 kk 組的效果在判定 kk 時已經算過了）。

那如何把 log⁡m\log m 壓掉呢？

只要換個掃描順序：從左到右處理每個位置，維護三個狀態：

  • 已加入的查詢數：答案候選，初始為 00
  • 差分陣列：已加入的查詢對後續位置的影響標記
  • 當前累積額度：目前位置從已加入查詢中拿到的總減少額度

處理一個位置時，先從差分陣列取得該位置的新增額度，更新當前累積額度。

  • 若累積額度已足夠覆蓋該位置的初始值：直接看下一個位置。
  • 若累積額度不夠：只能繼續追加後續查詢，直到額度滿足為止。
為什麼只能追加？

答案要求使用查詢前綴，不能跳過前面的查詢，也不能改變查詢順序。當前位置不夠時，追加下一組查詢是唯一選擇。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m) —— 每個位置和每組查詢最多處理一次
  • 空間複雜度：O(n)\mathcal{O}(n) —— 差分陣列

方法三：線段樹維護全域最大值

還有一個比較直接的寫法：既然每次查詢可以讓區間內每個位置最多減少某個值，為了盡快歸零，直接把區間內所有元素減去該值不會變差（減多了只會讓元素更小，題目允許 ≤0\le 0）。

問題變成：

依序做區間減法，問什麼時候全域最大值 ≤0\le 0。

這是線段樹的標準模型：區間加法 + 查詢全域最大值。每次對區間加上一個負值，更新後若根節點最大值 ≤0\le 0，當前查詢數就是答案。需要特判一開始就全是 00 的情況（答案為 00）。

複雜度分析

  • 時間複雜度：O(n+mlog⁡n)\mathcal{O}(n + m\log n) —— 建樹 O(n)\mathcal{O}(n)，每組查詢 O(log⁡n)\mathcal{O}(\log n)
  • 空間複雜度：O(n)\mathcal{O}(n) —— 線段樹

類題

Code

方法一：二分答案 + 差分陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)

        def check(k):
            diff = [0] * (n + 1)
            for l, r, v in queries[:k]:
                diff[l] += v
                diff[r + 1] -= v
            return all(s >= x for s, x in zip(accumulate(diff), nums))

        left, right = 0, m
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left if left <= m else -1

方法二：雙指標 + 差分陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)
        diff = [0] * (n + 1)
        s = k = 0
        for i, x in enumerate(nums):
            s += diff[i]
            while k < m and s < x:
                l, r, v = queries[k]
                diff[l] += v
                diff[r + 1] -= v
                if l <= i <= r:
                    s += v
                k += 1
            if s < x:
                return -1
        return k

方法三：線段樹（區間加法 + 全域最大值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        sz = 2 << n.bit_length()
        tree = [0] * sz
        lazy = [0] * sz

        def build(o: int, left: int, right: int) -> None:
            if left == right:
                tree[o] = nums[left]
                return
            mid = (left + right) // 2
            build(o * 2, left, mid)
            build(o * 2 + 1, mid + 1, right)
            pushup(o)

        def pushup(o: int) -> None:
            tree[o] = max(tree[o * 2], tree[o * 2 + 1])

        def _update(o: int, left: int, right: int, v: int) -> None:
            tree[o] += v
            lazy[o] += v

        def pushdown(o: int, left: int, right: int) -> None:
            if lazy[o] == 0 or left == right:
                return
            mid = (left + right) // 2
            _update(o * 2, left, mid, lazy[o])
            _update(o * 2 + 1, mid + 1, right, lazy[o])
            lazy[o] = 0

        def update(o: int, left: int, right: int, l: int, r: int, f: Any) -> None:
            if l <= left and right <= r:
                _update(o, left, right, f)
                return
            pushdown(o, left, right)
            mid = (left + right) // 2
            if l <= mid:
                update(o * 2, left, mid, l, r, f)
            if r > mid:
                update(o * 2 + 1, mid + 1, right, l, r, f)
            pushup(o)

        def apply(l: int, r: int, f: Any) -> None:
            if l > r:
                return
            update(1, 0, n - 1, l, r, f)

        build(1, 0, n - 1)
        if tree[1] <= 0:
            return 0

        for i, (l, r, v) in enumerate(queries, start=1):
            apply(l, r, -v)
            if tree[1] <= 0:
                return i
        return -1