题目描述

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [l_i, r_i, val_i]。

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

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

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

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

输入： 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^5
• 0 <= nums[i] <= 5 * 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 3
• 0 <= l_i <= r_i < nums.length
• 1 <= val_i <= 5

算法

(二分答案，差分数组) $O((n + q) \log q)$

1. 最终的 $k$ 显然是一个单调的划分，故可以通过二分答案确定 $k$ 的位置。
2. 假设给定到第 $mid$ 个查询，然后判断是否可以通过前 $mid$ 个操作满足条件。
3. 对于每个查询，都在其左端点的位置增加 $val_i$，在右端点的 下一个 位置减少 $val_i$。
4. 然后求上述操作后的每个位置的前缀和，其值就是这个位置最多可以被减少的数值。

时间复杂度

• 二分的上下界为 $q$。
• 每次判定的时间复杂度为 $O(n + q)$。
• 故总时间复杂度为 $O((n + q) \log q)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储差分数组。

C++ 代码

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size();

        auto check = [&](int t) {
            vector<int> p(n + 1, 0);
            for (int i = 0; i < t; i++) {
                p[queries[i][0]] += queries[i][2];
                p[queries[i][1] + 1] -= queries[i][2];
            }

            int s = 0;
            for (int i = 0; i < n; i++) {
                s += p[i];
                if (s < nums[i])
                    return false;
            }

            return true;
        };

        int l = 0, r = queries.size() + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }

        return l == queries.size() + 1 ? -1 : l;
    }
};