LeetCode 3356.零数组变换 II：二分查找 + I的差分数组

【LetMeFly】3356.零数组变换 II：二分查找 + I的差分数组

力扣题目链接：https://leetcode.cn/problems/zero-array-transformation-ii/

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

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

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

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

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

示例 1：

输出： 2

解释：

• 对于 i = 0（l = 0, r = 2, val = 1）：

  <ul>
  	<li>在下标&nbsp;<code>[0, 1, 2]</code> 处分别减少 <code>[1, 0, 1]</code>。</li>
  	<li>数组将变为 <code>[1, 0, 1]</code>。</li>
  </ul>
  </li>
  <li><strong>对于 i = 1（l = 0, r = 2, val = 1）：</strong>
  <ul>
  	<li>在下标&nbsp;<code>[0, 1, 2]</code> 处分别减少 <code>[1, 0, 1]</code>。</li>
  	<li>数组将变为 <code>[0, 0, 0]</code>，这是一个零数组。因此，<code>k</code> 的最小值为 2。</li>
  </ul>
  </li>
  

示例 2：

输出： -1

解释：

• 对于 i = 0（l = 1, r = 3, val = 2）：

  <ul>
  	<li>在下标&nbsp;<code>[1, 2, 3]</code> 处分别减少 <code>[2, 2, 1]</code>。</li>
  	<li>数组将变为 <code>[4, 1, 0, 0]</code>。</li>
  </ul>
  </li>
  <li><strong>对于 i = 1（l = 0, r = 2, val = 1）：</strong>
  <ul>
  	<li>在下标&nbsp;<code>[0, 1, 2]</code> 处分别减少 <code>[1, 1, 0]</code>。</li>
  	<li>数组将变为 <code>[3, 0, 0, 0]</code>，这不是一个零数组。</li>
  </ul>
  </li>
  

提示：

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

解题方法：xx

首先请解决3355.零数组变换 I。

在I中，我们可以在$O(m+n)$的时间内判断能否将所有数全变为小于等于0。

这道题多加个二分查找就可以了。因为所执行query越多，就越能变成零数组。

二分时候可以使用左右开区间，有效范围是$(l,r)$。当$l+1==r$时结束循环，$r$（或-1）即为答案

• 时间复杂度$O((m+n)\log n)$，其中$m=len(nums)$，$n=len(queries)$
• 空间复杂度$O(\log queries)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-05-22 13:41:00
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-22 23:16:48
 */
class Solution {
private:
    bool ok(vector<int>& nums, vector<vector<int>>& queries, int t) {
        vector<int> diff(nums.size() + 1);
        for (int i = 0; i < t; i++) {
            diff[queries[i][0]] += queries[i][2];
            diff[queries[i][1] + 1] -= queries[i][2];
        }
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            cnt += diff[i];
            if (nums[i] > cnt) {
                return false;
            }
        }
        return true;
    }
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int l = -1, r = queries.size() + 1;  // (l, r)
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (ok(nums, queries, m)) {
                r = m;
            } else {
                l = m;
            }
        }
        return r > queries.size() ? -1 : r;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-05-22 22:07:10
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-22 23:27:03
'''
from typing import List

class Solution:
    def check(self, n: int) -> bool:
        diff = [0] * (len(self.nums) + 1)
        for l, r, v in self.queries[:n]:
            diff[l] += v
            diff[r + 1] -= v
        cnt = 0
        for i in range(len(self.nums)):
            cnt += diff[i]
            if self.nums[i] > cnt:
                return False
        return True

    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        self.nums = nums
        self.queries = queries
        l, r = -1, len(queries) + 1
        while l + 1 < r:
            m = (l + r) >> 1
            if self.check(m):
                r = m
            else:
                l = m
        return -1 if r > len(queries) else r

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-05-22 22:07:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-22 23:29:09
 */
class Solution {
    private int[] nums;
    private int[][] queries;

    public boolean check(int n) {
        int[] diff = new int[nums.length + 1];
        for (int i = 0; i < n; i++) {
            diff[queries[i][0]] += queries[i][2];
            diff[queries[i][1] + 1] -= queries[i][2];
        }
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            cnt += diff[i];
            if (nums[i] > cnt) {
                return false;
            }
        }
        return true;
    }

    public int minZeroArray(int[] nums, int[][] queries) {
        this.nums = nums;
        this.queries = queries;
        int l = -1, r = queries.length + 1;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        return r > queries.length ? -1 : r;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-05-22 22:07:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-22 23:33:57
 */
package main

func check3356(nums []int, queries [][]int, n int) bool {
	diff := make([]int, len(nums) + 1)
	for _, q := range queries[:n] {
		diff[q[0]] += q[2]
		diff[q[1] + 1] -= q[2]
	}
	cnt := 0
	for i := range nums {
		cnt += diff[i]
		if nums[i] > cnt {
			return false
		}
	}
	return true
}

func minZeroArray(nums []int, queries [][]int) int {
    l, r := -1, len(queries) + 1
	for l + 1 < r {
		m := (l + r) >> 1
		if check3356(nums, queries, m) {
			r = m
		} else {
			l = m
		}
	}
	if r > len(queries) {
		return -1
	}
	return r
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源