3356. 零数组变换 II

🟠   🔖  数组 二分查找 前缀和  🔗 力扣 LeetCode

题目

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri, vali].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [li, ri] in nums by at most vali.
• The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence , nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

Input: nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

Output: 2

Explanation:

• For i = 0 (l = 0, r = 2, val = 1):

  • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.

  • The array will become [1, 0, 1].

• For i = 1 (l = 0, r = 2, val = 1):

  • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.

  • The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

Input: nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]

Output: -1

Explanation:

• For i = 0 (l = 1, r = 3, val = 2):

  • Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
  • The array will become [4, 1, 0, 0].

• For i = 1 (l = 0, r = 2, val = 1):

  • Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
  • The array will become [3, 0, 0, 0], which is not a Zero Array.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 5 * 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 3
• 0 <= li <= ri < nums.length
• 1 <= vali <= 5

题目大意

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

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

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

零数组 是指所有元素都等于 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^5
• 0 <= nums[i] <= 5 * 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 3
• 0 <= li <= ri < nums.length
• 1 <= vali <= 5

解题思路

由于查询操作是累积的，每个 queries[i] 只能减少 nums 的值，因此：

• 如果 k 能使 nums 全部变成 0，那么更大的 k' > k 也一定可以。
• 如果 k 不能使 nums 全 0，那么更小的 k' < k 也不行。

可以 二分 k 来找到最小的 k。

1. 判断是否能使 nums 全部变 0（canMakeZero(k)）

   使用差分数组加速区间修改：

   • 初始化 prefixSum，大小 n + 1，用于记录增减操作。
   • 遍历 queries[0:k]：
     • 对 prefixSum[l] 加 val（区间增加 val）。
     • 对 prefixSum[r+1] 减 val（区间结束，抵消之前的 val）。
   • 计算前缀和：
     • sum[i] 记录当前元素 nums[i] 累积的 val 变化。
     • 若 nums[i] - sum[i] > 0，说明 nums[i] 仍然是正数，不可能全部变 0，返回 false。
   • 若 nums 都能变成 0，返回 true。

2. 二分查找 k

   • left = 0, right = m，搜索 0 ≤ k ≤ m。
   • 取中点 mid = (left + right) / 2：
     • 若 canMakeZero(mid) 为 true，说明可以用更小的 k，缩小 right。
     • 否则 k 太小了，需要增大，调整 left。
   • 结束时，返回 left，若 left > m，则返回 -1（无法使 nums 变 0）。

复杂度分析

• 时间复杂度：O((n + m) log m)，其中 n = nums.length，m = queries.length。
• 空间复杂度：O(n)，用于 prefixSum。

代码

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number}
 */
var minZeroArray = function (nums, queries) {
	const n = nums.length;
	const m = queries.length;
	const canMakeZero = (k) => {
		let prefixSum = new Array(n + 1).fill(0);

		for (let i = 0; i < k; i++) {
			const [l, r, val] = queries[i];
			prefixSum[l] += val;
			prefixSum[r + 1] -= val;
		}

		let sum = 0;
		for (let i = 0; i < n; i++) {
			sum += prefixSum[i];
			if (nums[i] - sum > 0) {
				return false;
			}
		}
		return true;
	};

	let left = 0,
		right = m;
	while (left <= right) {
		const mid = ((left + right) / 2) | 0;
		if (canMakeZero(mid)) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return left > m ? -1 : left;
};

相关题目

题号	标题	题解	标签	难度	力扣
1109	航班预订统计		数组 前缀和	🟠	🀄️ 🔗
1674	使数组互补的最少操作次数		数组 哈希表 前缀和	🟠	🀄️ 🔗