Skip to content

Latest commit

 

History

History
230 lines (156 loc) · 7 KB

3356.md

File metadata and controls

230 lines (156 loc) · 7 KB
title description keywords
3356. 零数组变换 II
LeetCode 3356. 零数组变换 II题解，Zero Array Transformation II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
3356. 零数组变换 II
零数组变换 II
Zero Array Transformation II
解题思路
数组
二分查找
前缀和

3356. 零数组变换 II

🟠 Medium  🔖  数组 二分查找 前缀和  🔗 力扣 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 使数组互补的最少操作次数 数组 哈希表 前缀和 🟠 🀄️ 🔗