LeetCode每日一题2025-05-21

点击获取AI摘要

3356. 零数组变换 II M

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [lᵢ, rᵢ, valᵢ]。

每个 queries[i] 表示在 nums 上执行以下操作：

• 将 nums 中 [lᵢ, rᵢ] 范围内的每个下标对应元素的值 最多 减少 valᵢ。
• 每个下标的减少的数值可以独立选择。

零数组 是指所有元素都等于 0 的数组。

返回 k 可以取到的 最小非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。

示例 1：

输入： nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

输出： 2

解释：

• 对于 i = 0（l = 0, r = 2, val = 1）：
  • 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
  • 数组将变为 [1, 0, 1]。
• 对于 i = 1（l = 0, r = 2, val = 1）：
  • 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
  • 数组将变为 [0, 0, 0]，这是一个零数组。因此，k 的最小值为 2。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]

输出： -1

解释：

• 对于 i = 0（l = 1, r = 3, val = 2）：
  • 在下标 [1, 2, 3] 处分别减少 [2, 2, 1]。
  • 数组将变为 [4, 1, 0, 0]。
• 对于 i = 1（l = 0, r = 2, val = 1）：
  • 在下标 [0, 1, 2] 处分别减少 [1, 1, 0]。
  • 数组将变为 [3, 0, 0, 0]，这不是一个零数组。

提示：

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 5 * 10⁵
• 1 <= queries.length <= 10⁵
• queries[i].length == 3
• 0 <= lᵢ <= rᵢ < nums.length
• 1 <= valᵢ <= 5

问题分析

要找最小的 $k$ ，使得对 nums 执行前 $k$ 条查询后，可以将数组完全凑成“零数组”。每条查询 $[l_i,\,r_i,\,v_i]$ 表示在区间 $[l_i,r_i]$ 内，各下标位置最多各自减少 $v_i$，每个位置可以独立选减少多少。

我们定义一个“剩余需求”数组 $\mathrm{rem}[i]$，它表示下标 iii 要变成 0，还需要从查询里“累计扣除”多少。
初始时 $\mathrm{rem}[i] = \texttt{nums}[i]$。随着我们“依次”处理第 1 条、第 2 条、…、第 $k$ 条查询，每执行一条查询，就要把它对区间 $[l,r]$ 内的 $\mathrm{rem}$ 统一**“减去”** $v$（注意：如果该条查询本身要求的 $v$ 大于 $\mathrm{rem}[i]$，其实“最多”减 $v$ 的含义对应我们在代码里直接减；因为之后我们会在 $\mathrm{rem}[i] \le 0$ 时“收集答案”并且把它标记为不再参与后续运算——详见下文）。

当且仅当某个位置 $i$ 经历了若干次涵盖它的查询以后，$\mathrm{rem}[i]$ 的值变得 $\le 0$，就说明“对下标 $i$ 而言，它已经完全被扣成 0 了”。我们记录下最先使得 $\mathrm{rem}[i]$ “跨到 $\le 0$”的那条查询的编号 $idx$，记为 $\mathrm{ans}[i] = idx$。如果直到所有 $m$ 条查询都跑完，它仍未被扣到 $\le 0$，则 $\mathrm{ans}[i]=+\infty$ （或用 $-1$ 表示“永远扣不成 0”）。

最后，只要所有下标都能在某个时刻“跨到 $\le0$”，那么整个数组才能凑成零。令

$$K = \max_{0 \le i < n}\; \mathrm{ans}[i]\,.$$

如果 $K \le m$，则答案就是 $K$；否则（存在某个位置从未走到 $\le0$），答案返回 $-1$。

算法思路

区间减与“找最小非正下标”

“给 $\mathrm{rem}[\,]$ 做一次 $[l,r]$ 区间统一减 $v$”

“询问当前整个数组 $\mathrm{rem}[\,]$ 的最小值，检查它是否 $\le 0$；如果是，把那个位置取出来，记录答案，并把它从后续运算中剔除。”

要想在每执行一条查询之后，快速做到“把 $\mathrm{rem}[l \ldots r]$ 整个区间都减掉 $v$”，并能检查是否有位置跨到 $\leq 0$，最常用的办法就是线段树（带懒标记）的“区间减一次，区间查询最小值”。具体思路如下：

我们把 $\mathrm{rem}[]$ 维护在一棵线段树上，线段树的每个节点记录该区间当前的最小 rem 值（即 minv），同时支持“区间减去 $v$”的懒标记（节点上加一个 lazy 值表示要向下传递的减量）。

我们还需要一个额外操作：“如果整个区间的最小值 $\leq 0$，就找出一个下标 $i$，使得 $\mathrm{rem}[i] \leq 0$。”

由于线段树根节点存储了全区间（$0..n-1$）的最小值，即 $\text{tree}[1].\text{minv}$，只要 $\text{tree}[1].\text{minv} \leq 0$，就说明至少有一个叶子节点 $i$ 满足 $\mathrm{rem}[i] \leq 0$。

此时我们可以从根节点向下递归：

• 如果左子节点的 minv $\leq 0$，就优先进入左子树，否则进入右子树。

• 不断递归，直到定位到某个叶节点 $i$，它的 minv $\leq 0$，这就是当前“最小 rem $\leq 0$”对应的下标。

找到 $i$ 之后，我们将线段树中 $\mathrm{rem}[i]$ 设为一个很大的正数（比如 $+\infty$，实际代码里用足够大的常数 $\text{INF}=10^{18}$）。这样，相当于把 $i$ 从后续所有区间减法操作中移除，该下标不再参与后面的判 $\leq 0$ 检查。

只要“线段树根节点 minv $\leq 0$”，就不断进行“找 $i$，将 $\mathrm{rem}[i]$ 置 $+\infty$，并记录 $\text{ans}[i]=\text{当前查询编号}$”操作；循环直到根节点最小值 $>0$，然后进入下一条查询。

时间复杂度

1. 线段树建树 $O(n)$。

2. 先把 $\mathrm{nums}[i]=0$ 的那些下标提取一次，总共操作次数最多 $n$ 次“找 $\le 0$ + 单点置 $\mathrm{INF}$”，每次 $O(\log n)$，合计 $O(n \log n)$。

3. 针对 $m$ 条查询，每条：

   1. 区间减一次 $O(\log n)$。
   2. 紧接着最多有若干个新下标跨到 $\mathrm{rem} \le 0$，反复做“找 $i$ + 置 $\mathrm{INF}$” 若干次。
      • 每个下标 $i$ 只会从 $\mathrm{rem}>0$ 变到 $\mathrm{rem}\le 0$ 一次，因此所有“找 $i$ 并置 $\mathrm{INF}$”操作总共不会超过 $n$ 次，每次 $O(\log n)$。

4. 所以总复杂度为：

   • 建树 $O(n)$
   • 查找与置 $\mathrm{INF}$ 总共 $O(n \log n)$
   • 区间减 $m$ 次 $O(m \log n)$
   • 最终为 $O((n+m)\log n)$

• 空间复杂度 $O(n)$，主要用于 $\mathrm{rem}$、$\mathrm{ans}$ 以及线段树节点（最多约 $4n$）。

代码分解

1. 初始化

• 读入 $n = \mathrm{len(nums)}$，$m = \mathrm{len(queries)}$。

• 用一个数组 $\mathrm{rem}$，大小 $n$，令 $\mathrm{rem}[i] = \mathrm{nums}[i]$。

• 用一个大小为 $n$ 的答案数组 $\mathrm{ans}$，全部初始化成 $\mathrm{INF}$（或者 $m+1$，表示“还没被扣到 $\le 0$”）。

• 提前把所有 $i$ 且 $\mathrm{rem}[i] = 0$ 的下标视作“在第 $0$ 条查询就能扣到 $\le 0$”：

  • 构建一棵线段树，把每个叶子节点的初始值设成 $\mathrm{rem}[i]$。

  • 线段树内置“最小值”信息，建完之后如果根节点 $\mathrm{minv} == 0$，就说明某些下标初始就 $\mathrm{rem}=0$。我们要在第 $0$ 步（即不执行任何查询）就把它们提取：

    while tree_root.minv ≤ 0:
        i = query_index_of_some_leaf_with_minv≤0()
        ans[i] = 0
        update_leaf(i, +INF)   # 把 rem[i] 设为 +INF，等于“干掉它”

  • 这样，所有初始 $\mathrm{nums}[i]=0$ 的位置就有了 $\mathrm{ans}[i]=0$。

2. 按查询编号 $1..m$ 依次处理

对于当前处理到第 $idx$（1-based）的查询 $\mathrm{queries}[idx-1] = [l, r, v]$，执行：

• 在线段树上对区间 $[l, r]$ 做“整体再减 $v$” （用懒标记方式）。

• 更新完毕后，检查线段树的根节点 $\mathrm{minv}$ 是否 $\le 0$：

  • 如果 $\mathrm{minv} > 0$，说明这时候没有任何下标的 $\mathrm{rem} \le 0$，直接跳到下一条查询（$idx += 1$）。

  • 否则，反复循环：

    while tree_root.minv ≤ 0:
        i = 找到某个叶子下标 i，使得 rem[i] ≤ 0
        ans[i] = idx
        update_leaf(i, +INF)   # 将该位置从后续考虑中剔除

  • 上述循环结束代表此时所有还在树里的“rem”都已 $> 0$，可以处理下一条查询。

3. 遍历结束后，计算最终答案

• 对 $\mathrm{ans}[i]$ 做一次遍历：如果有下标 $i$ 永远都没被扣到 $\le 0$（即 $\mathrm{ans}[i]$ 保持初始的 $\mathrm{INF}$），说明它不可能凑成零，直接返回 $-1$。
• 否则，答案 $K = \max_{0 \le i < n} \mathrm{ans}[i]$。返回此 $K$。

4. 我们需要实现一个支持以下操作的线段树（0-based）：

5. 建树（build）：把初始数组 $\mathrm{rem}[]$ 的值装进去，构建出“每个区间的最小值”。

6. 区间减 $(ql, qr, v)$：在 $[ql, qr]$ 这段，所有 $\mathrm{rem}[i]$ 都要再减去 $v$。

   • 通过在节点打“懒标记 $\mathrm{lz}[node] += v$”让该节点下所有值都“虚拟地”减 $v$，并在需要时把懒标记下传给左右子节点。

7. 询问全局最小 (query_min())：直接从根节点读出 $\mathrm{tree}[1].\mathrm{minv}$。

8. 找某个满足 $\mathrm{rem}[i]\leq 0$ 的下标 $i$：

   • 如果当前根节点的 $\mathrm{minv} > 0$，说明没有任何 $\le 0$ 的叶子，直接返回“无”。
   • 否则从根节点开始，若左子节点的 $\mathrm{minv} \leq 0$ 就往左子树走；否则往右子树。直到到叶子，拿到具体下标 $i$。

9. 把一个下标 $i$“标记为已完成”：在叶子层将 $\mathrm{rem}[i]$ 直接置 $\mathrm{INF}$（足够大的正数），然后向上拉一次更新父节点的最小值。这样后续它就不会再被判 $\le 0$。

由于 $n\le 10^{5}$，线段树最多需要 $4n$ 个节点。所有操作的单次复杂度都是 $O(\log n)$。

代码实现

初始化时把 $\mathrm{nums}[i]=0$ 的下标提前提取

• 一开始建树完毕后，就把所有 $\mathrm{rem}[i] == 0$ 的下标（也就是原始 $\mathrm{nums}[i]$ 已经是 $0$）用“查询编号 $0$”直接记录在 $\mathrm{ans}[i]$，然后在树里把 $\mathrm{rem}[i]$ 设为 $\mathrm{INF}$（等价于把它从后续所有区间操作和“再查 $\le 0$”中干掉）。
• 这样做的好处是：如果某个位置原本就是 $0$，就不需要等待任何真正的查询，它的答案就是 $0$。

每条查询后“区间整体再减 $v$”

• 使用线段树带懒标记的区间减操作 $\mathrm{range\_sub}(1, 0, n-1, l, r, v)$，单次复杂度 $O(\log n)$。
• 更新完毕以后，只需要检查树根的最小值 $\mathrm{query\_global\_min}()$ 是否 $\le 0$。
  • 如果 $> 0$，说明目前没有新的下标变得 $\mathrm{rem} \le 0$，直接进入下一条查询。
  • 否则，循环“找一个 $\le 0$ 的叶子” $i_0 = \mathrm{find\_any\_nonpos}(1, 0, n-1)$，把它的 $\mathrm{ans}[i_0]$ 设为当前查询编号 $idx$，再在树里把 $\mathrm{rem}[i_0]=\mathrm{INF}$，并向上更新维护最小值。循环直到树根最小值 $> 0$。

最后的答案 $K$

• 只要所有 $i$ 都在某个时刻跨到 $\mathrm{rem}[i] \le 0$，它们的 $\mathrm{ans}[i]$ 就是一个落在 $[0..m]$ 的整数。此时答案 $K = \max_i \mathrm{ans}[i]$。
• 如果有某个 $\mathrm{ans}[i]$ 始终保持 $\mathrm{INF}$，说明它从来没被扣到 $\le 0$，返回 $-1$。

class SegmentTree:
    def __init__(self, arr: list):
        self.n = len(arr)
        self.minv = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.INF = 10**18

        def build(node, l, r):
            if l == r:
                self.minv[node] = arr[l]
            else:
                mid = (l + r) // 2
                build(node * 2, l, mid)
                build(node * 2 + 1, mid + 1, r)
                self.minv[node] = min(self.minv[node * 2], self.minv[node * 2 + 1])

        build(1, 0, self.n - 1)

    def _apply_lazy(self, node, delta):
        self.minv[node] -= delta
        self.lazy[node] += delta

    def _push_down(self, node):
        if self.lazy[node] != 0:
            delta = self.lazy[node]
            self._apply_lazy(node * 2, delta)
            self._apply_lazy(node * 2 + 1, delta)
            self.lazy[node] = 0

    def _push_up(self, node):
        self.minv[node] = min(self.minv[node * 2], self.minv[node * 2 + 1])

    def range_sub(self, node, l, r, ql, qr, v):
        if ql <= l and r <= qr:
            self._apply_lazy(node, v)
            return

        self._push_down(node)
        mid = (l + r) // 2
        if qr <= mid:
            self.range_sub(node * 2, l, mid, ql, qr, v)
        elif ql > mid:
            self.range_sub(node * 2 + 1, mid + 1, r, ql, qr, v)
        else:
            self.range_sub(node * 2, l, mid, ql, qr, v)
            self.range_sub(node * 2 + 1, mid + 1, r, ql, qr, v)

        self._push_up(node)

    def query_global_min(self):
        return self.minv[1]

    def find_any_nonpos(self, node, l, r):
        if self.minv[node] > 0:
            return -1
        if l == r:
            return l

        self._push_down(node)
        mid = (l + r) // 2
        if self.minv[node * 2] <= 0:
            return self.find_any_nonpos(node * 2, l, mid)
        else:
            return self.find_any_nonpos(node * 2 + 1, mid + 1, r)

    def set_inf(self, node, l, r, idx):
        if l == r:
            self.minv[node] = self.INF
            return

        self._push_down(node)
        mid = (l + r) // 2
        if idx <= mid:
            self.set_inf(node * 2, l, mid, idx)
        else:
            self.set_inf(node * 2 + 1, mid + 1, r, idx)

        self._push_up(node)


class Solution:
    def minZeroArray(self, nums, queries):
        n = len(nums)
        m = len(queries)
        rem = nums[:]
        INF = 10**18
        ans = [INF] * n
        st = SegmentTree(rem)

        # 处理原本就为0的下标
        while True:
            if st.query_global_min() > 0:
                break
            i0 = st.find_any_nonpos(1, 0, n - 1)
            if i0 == -1:
                break
            ans[i0] = 0
            st.set_inf(1, 0, n - 1, i0)

        # 依次处理每条查询
        for idx in range(1, m + 1):
            l, r, v = queries[idx - 1]
            st.range_sub(1, 0, n - 1, l, r, v)
            while True:
                if st.query_global_min() > 0:
                    break
                i0 = st.find_any_nonpos(1, 0, n - 1)
                if i0 == -1:
                    break
                if ans[i0] == INF:
                    ans[i0] = idx
                st.set_inf(1, 0, n - 1, i0)

        # 检查是否全部 <= 0
        final_ans = 0
        for i in range(n):
            if ans[i] == INF:
                return -1
            final_ans = max(final_ans, ans[i])
        return final_ans

算法思路2

1. 差分+验证模型

   • 对于某个固定的 k（只考虑前 k 条查询），要判断是否能把 nums 完全减为 0，需要检查每个位置 i 在这 k 条查询中，允许的“最大累计减量”之和是否 $\geq nums[i]$。

   • 原因：每个查询在覆盖区间 [l, r] 内，对位置 i 可以最多减去 v；若该位置被多条查询覆盖，那么这些查询各自能提供的“最大减量额度”加起来，就形成了“可用的整体减量上限”。只有当前 k 条查询对位置 i 的“减量额度之和” $\geq$ nums[i]，才能让它有机会被减到 0。

   • 判定条件转化为：

     定义数组 $cap[i] = \sum_{j=0}^{k-1,\ l_j \leq i \leq r_j} v_j$。
     如果对所有 i 都有 cap[i] $\geq$ nums[i]，则这 k 条查询可以通过合理分配将 nums 全部扣为 0。否则不能。

2. 计算 cap[]——差分+前缀和

   • 维护一个长度为 n+1 的差分数组 diff，初始化全为 0。

   • 对于查询 [l, r, v]（下标从 0 开始），做：

     diff[l] += v
     diff[r+1] -= v

   • 所有前 k 条查询都更新后，对 diff 做一次前缀和，在线性时间 $O(n)$ 内得到每个位置 i 的 cap[i]。

   • 最后只需检验：对每个 i，cap[i] $\geq$ nums[i] 吗？

3. 二分查找

   • 如果对于某个 k₀ 满足“前 k₀ 条查询可以凑出零数组”，则对于任何 $k \geq k_0$，cap[i] 只会更大，所以“可行性”是单调的。
   • 可在 [0, m] 区间二分，找第一个可行的 k。若整个区间都不可，返回 -1。

4. 实现思路

   • 定义函数 check(k)：判断前 k 条查询能否凑成零数组
     a. 初始化长度为 n+1 的 diff 数组，全 0。
     b. 对于 j=0…k-1，每条 $[l_j, r_j, v_j]$：执行 $diff[l_j] += v_j$，$diff[r_j+1] -= v_j$。
     c. 对 diff 做前缀和，得到 cap 数组长度为 n：cap[i] = 能够提供给位置 i 的累计减量额度。
     d. 遍历 i=0…n-1，如果 cap[i] < nums[i]，直接返回 False；否则全部通过返回 True。

   • 在主函数，对 k 在 [0, m] 做二分：

     a. lo = 0, hi = m, answer = m+1。
     b. while lo $\leq$ hi：
         mid = (lo+hi)//2
         if check(mid)：answer = mid; hi = mid-1
         else：lo = mid+1
     c. 最终如果 answer $$\leq$$ m 则返回 answer，否则返回 -1。

   • 允许 k = 0 进入 check(0)：没有任何查询时，只有当 nums 全为 0 才判通过。

时间复杂度

• 一次 check(k)：$O(n + k)$。
• 二分最多调用 $O(\log m)$ 次。
• 总复杂度：$O((n+m)\log m)$。

空间复杂度

• 差分数组 diff 长度 n+1，cap 长度 n，以及 zerolithx 变量，$O(n)$。

from typing import List

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        m = len(queries)
        
        # 检查函数：检查前 k 条查询能否把 nums 减为零数组
        def check(k: int) -> bool:
            # 差分数组，长度 n+1，初始全 0
            diff = [0] * (n + 1)
            
            # 如果 k > 0，则把前 k 条查询都叠加到 diff 上
            for idx in range(k):
                l, r, v = queries[idx]
                diff[l] += v
                if r + 1 < n:
                    diff[r + 1] -= v
            
            # 前缀和得到 cap[i]，并随即验证 cap[i] 是否 >= nums[i]
            running = 0
            for i in range(n):
                running += diff[i]
                # cap[i] = running
                if running < nums[i]:
                    return False
            return True
        
        # 在 k ∈ [0, m] 上二分，寻找最小的 k 使 check(k) 为 True
        lo, hi = 0, m
        answer = m + 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                answer = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        return answer if answer <= m else -1

算法思路3

我们需要求出最小的 $k$，使得“前 $k$ 条查询”能够同时满足

$$\forall\,0 \le i < n,\quad \sum_{\substack{0 \le j < k \\ l_j \le i \le r_j}} v_j \;\; \ge\; nums[i].$$

如果把

$$\text{cap}[i](k) \;=\; \sum_{\substack{0 \le j < k \\ l_j \le i \le r_j}} v_j$$

看作“在下标 $i$ 处，前 $k$ 条查询最多能提供的扣减总量”，那么题目要求找最小 $k$ 使得$\text{cap}[i](k) \ge nums[i],\,\forall i$。
这本质上等同于：对每个 $i$，我们单独去看“最早满足 $\text{cap}[i](k) \ge nums[i]$ 的那个 $k_i$”；答案就是

$$k = \max_{0 \le i < n} k_i$$

（如果某个位置永远加不够，那整个答案就是 $-1$。）

• 贪心地求出每个 $k_i$ 的思路

  • 把下标 $i$ 从 $0$ 到 $n-1$ 依次“排队”，

  • 维护一个“差分数组” cnt[0..n]，它可以让我们以 $O(1)$ 的方式“把新的一条查询 $[a, b, v]$ 加入到以后所有下标的可用额度里”：

    • cnt[a] += v; cnt[b+1] -= v，
    • 然后每推进一个下标 $i$ 时，只要做 s += cnt[i]，就能得到“前面已经加入到差分结构的那些查询，在位置 $i$ 处的总叠加额度”。

  • 于是，如果当前 s < nums[i]（说明已经加到差分里的查询还不够把 nums[i] 扣成 0），我们就继续把第 $j$ 条、第 $j+1$ 条……查询“投进来”——也就是执行

    cnt[a_j] += v_j
    cnt[b_j + 1] -= v_j

  在差分里给它记号，然后如果这条新加的查询确实覆盖到了位置 $i$（if a_j <= i <= b_j），就 s += v_j，因为此时“对 $i$”就立刻生效——把 s 补 $v_j$。

  • 只要 s 还小于 nums[i]，就再把下一条查询“投进来”，直到$s \ge nums[i]$ 或者$j == m$（查完所有查询）为止。
    • 如果 $s < nums[i]$ 而 $j == m$，说明“所有查询投完”都还是凑不够$nums[i]$，直接 return -1。
    • 否则在“退出 while”后，必然有 $s \ge nums[i]$，说明此时我们已经用了 $j$ 条查询第一个时刻让 $i$ 处达标。把这个“时刻”记下来，对更大的 $i$ 来说，我们不会再减 $j$，因为我们要保证所有小于当前 $i$ 的下标也都满足。在前面迭代过的所有 $i' < i$ 都已经被保证：它们的 “累计额度” $\le$ “我们此刻用的 $j$ 条查询的额度”，自然它们也都能凑够。
  • 最终结束所有 $i$ 后，$j$ 就是满足每个位置的需求（$\text{cap}[i] \ge nums[i]$）的 最小 查询数。
    • 若有任何一个 iii 走到一半就发现 $j$ 用光、又$s < nums[i]$，就 return -1。
    • 反之，最后返回的 $j$ 恰好等同于 $\max_i k_i$。

时间复杂度

• 外层 for i in range(n) 总共循环 n 次。
• 内部的 while j < m and s < nums[i]：
  • 每次循环体都会做一次 j += 1，因此 j 最多从 0 增加到 m，循环体总共进不超过 m 次。
  • 换句话说，所有 i 累积在一起，j 只会单调增长，从 0 到最多 m，绝不会回退或重复。
• 差分 cnt[a] += c; cnt[b+1] -= c; 是 $O(1)$ 操作。
• 每进 for i 一次，都先做 s += cnt[i]，也是 $O(1)$。
• 其余判断、下标范围判断、加法、比较都只是常数操作。

因此，总体的执行步骤：

1. 外层走 n 步（i = 0 … n-1）。
2. 内层的 j 累计至多走 m 步（从 j=0 一直加到不满足条件为止）。

没有任何嵌套导致 m 与 n 相乘，只是把这两段“线性扫描”交织在一起，最终耗时正好 $O(n + m)$。

代码实现

• n = len(nums)，m = len(queries)。

• cnt 是一个长度为 n+1 的「差分数组」，用于在 $O(1)$ 时间内模拟对任意区间 $[a,b]$ 做一次 “所有下标各自减去 c” 的操作。

  • 当我们想对 $[a, b]$ 区间整体去掉 “最多减 c” 这一额度时，就写

    cnt[a] += c
    cnt[b+1] -= c

  • 然后在遍历到下标 i 时，保留一个滚动变量 s，先做 s += cnt[i]，此时 s 就相当于 “下标 i 处所有已加入（也就是 j 之前的）查询对 i 的累积可用额度之和”。

• s： 表示“当前下标 i 被所有已用查询（前 j 条）覆盖时累计能减去的总量”。

• j：代表「已经把 queries[0], queries[1], …, queries[j-1] 这 j 条查询全部用到差分 cnt 里了」。

从 i=0 开始，遍历每个位置 i，保证在走到下标 i 时，s（累积能减的额度）足以满足 nums[i]。如果 s < nums[i]，就再从 queries[j] 开始把第 j 条、第 j+1 条……不断「添加到差分」直到让 s >= nums[i] 或者查询用完为止。一旦 s < nums[i] 并且 j == m（没有更多查询可加），就无法把 nums[i] 扣到 0，直接 return -1。如果所有 i 都能满足过，那么用到的查询数就是 j，返回它。

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)
        cnt = [0] * (n + 1)   # 差分数组，长度 n+1
        s = 0                 # 当前在下标 i 处的“累计已减”总量
        j = 0                 # 已经用了多少条查询

        for i in range(n):
            # 1) 先把差分 cnt[i] 累加到 s，得到“到下标 i 时，所有已用查询对 i 的累积贡献”：
            s += cnt[i]

            # 2) 如果到目前位置 i，s < nums[i]，说明“还不够把 nums[i] 扣成 0”
            #    那就从 queries[j] 开始，依次把第 j 条查询加进来，直到 s >= nums[i] 或 j 用完为止
            while j < m and s < nums[i]:
                a, b, c = queries[j]
                # 把 queries[j] 对区间 [a, b] 的“最多减 c”转化成差分:
                cnt[a] += c
                cnt[b + 1] -= c
                # 如果 i 恰好被 [a,b] 覆盖，那么要立刻把 s += c，因为在下标 i 处，这条查询就生效了
                if a <= i <= b:
                    s += c
                j += 1

            # 3) 退出 while 以后，要么 s >= nums[i]，说明“前 j 条查询对 i 的累计贡献至少 nums[i]”，可以把 nums[i] 扣到0；
            #    要么 j == m 且 s < nums[i]，说明所有查询都用完了，i 处还是扣不够，直接返回 -1
            if s < nums[i]:
                return -1

        # 4) 如果走到这里，说明对所有 0 ≤ i < n，都有 “前 j 条查询能把 nums[i] 扣成 0”。
        #    此时 j 就是最小 k，使得处理前 k 条查询后，nums 全部变成零数组。
        return j

差分数组 cnt + 滚动和 s

• 当我们刚进入循环、到达 i 时，用 s += cnt[i] 把“这一格的前缀差分”补上。
• 这样 s 始终表示“所有已经加进 cnt 的查询，对 i 这个位置在累计能减的总量”——与我们要的 $\text{cap}[i]$ 一一对应。

while j<m and s<nums[i] 里“如果 a≤i≤b 就 s += c”

• 这一步很重要：我们先在差分里做了 cnt[a]+=c; cnt[b+1]-=c，这保证了“从下标 a 开始”到“下标 b 结束”每个位置最终前缀和会多 c。
• 但是此时指针还在 i 上，如果 a ≤ i ≤ b，说明这个新加的区间 立刻影响 到了位置 i，所以 s 要马上加上那份 c。
• 如果 i < a 或者 i > b，新加的区间对 i 还不生效（会在后面 i 推到 a 时再生效，具体表现为执行到 i=a 后的 s += cnt[a] 就扣上去了）。

一旦 s < nums[i] 且 j==m，直接返回 -1

• 因为此时所有 m 条查询都加入到差分里，可是走到 i 时却依旧 s < nums[i]，说明在 所有查询 覆盖的累积额度下，nums[i] 也凑不成 0，后面没办法了。

最小性保证：贪心不会跳过更优解

• 你需要最小的 j，使得每个位置的“累积额度”都足够。如果在某个 i 上，s < nums[i]，你就一定要把 queries[j] 拿出来打一把，才能继续往前走——否则你根本没法保证这个 i 处的需求被满足。
• 你无法“跳过”某条查询，因为如果你不把它算在内，s 不可能「突然」跳到够用。
• 另一方面，一旦满足了 i，你也不会再撤回以前的查询——因为如果你撤回，就可能会让更小的下标变得不满足。但要想让 所有 下标都凑够，只能向右“多用”查询或者“用到恰好满足”为止。
• 因此你在 “遇到 i 还不够就把查询往里扔” 这一步上，实际上是严格按下标顺序寻找每个 i 的最早 “凑够它的那条查询编号”。这样遍历完所有 i，得到的 j 恰好就是最大的那一个“把 i 扣成 0 的查询编号”；也就是等同于 $\max_i k_i$。