登录
[Python3/Java/C++/Go/TypeScript] 一题一解：差分数组 + 二分查找（清晰题解）
2025年5月21日 06:15
方法一：差分数组 + 二分查找
我们注意到，查询的个数越多，越容易使得数组变成零数组，这存在单调性。因此，我们可以二分枚举查询的个数，判断在前 k 个查询下，是否可以将数组变成零数组。
我们定义二分查找的左边界 $l$ 和右边界 $r$，初始时 $l = 0$, $r = m + 1$，其中 $m$ 是查询的个数。我们定义一个函数 $\text{check}(k)$，表示在前 $k$ 个查询下，是否可以将数组变成零数组。我们可以使用差分数组来维护每个元素的值。
定义一个长度为 $n + 1$ 的数组 $d$，初始值全部为 $0$。对于前 $k$ 个查询的每个查询 $[l, r]$，我们将 $d[l]$ 加 $1$，将 $d[r + 1]$ 减 $1$。
然后我们遍历数组 $d$ 在 $[0, n - 1]$ 范围内的每个元素，累加前缀和 $s$，如果 $\textit{nums}[i] > s$，说明 $\textit{nums}$ 不能转换为零数组，返回 $\textit{false}$。
我们在二分查找的过程中，如果 $\text{check}(k)$ 返回 $\text{true}$，说明可以将数组变成零数组，我们就将右边界 $r$ 更新为 $k$，否则将左边界 $l$ 更新为 $k + 1$。
最后，我们判断 $l$ 是否大于 $m$，如果是，则返回 -1，否则返回 $l$。
###python
class Solution:
def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
def check(k: int) -> bool:
d = [0] * (len(nums) + 1)
for l, r, val in queries[:k]:
d[l] += val
d[r + 1] -= val
s = 0
for x, y in zip(nums, d):
s += y
if x > s:
return False
return True
m = len(queries)
l = bisect_left(range(m + 1), True, key=check)
return -1 if l > m else l
###java
class Solution {
private int n;
private int[] nums;
private int[][] queries;
public int minZeroArray(int[] nums, int[][] queries) {
this.nums = nums;
this.queries = queries;
n = nums.length;
int m = queries.length;
int l = 0, r = m + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
private boolean check(int k) {
int[] d = new int[n + 1];
for (int i = 0; i < k; ++i) {
int l = queries[i][0], r = queries[i][1], val = queries[i][2];
d[l] += val;
d[r + 1] -= val;
}
for (int i = 0, s = 0; i < n; ++i) {
s += d[i];
if (nums[i] > s) {
return false;
}
}
return true;
}
}
###cpp
class Solution {
public:
int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int d[n + 1];
int m = queries.size();
int l = 0, r = m + 1;
auto check = [&](int k) -> bool {
memset(d, 0, sizeof(d));
for (int i = 0; i < k; ++i) {
int l = queries[i][0], r = queries[i][1], val = queries[i][2];
d[l] += val;
d[r + 1] -= val;
}
for (int i = 0, s = 0; i < n; ++i) {
s += d[i];
if (nums[i] > s) {
return false;
}
}
return true;
};
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
};
###go
func minZeroArray(nums []int, queries [][]int) int {
n, m := len(nums), len(queries)
l := sort.Search(m+1, func(k int) bool {
d := make([]int, n+1)
for _, q := range queries[:k] {
l, r, val := q[0], q[1], q[2]
d[l] += val
d[r+1] -= val
}
s := 0
for i, x := range nums {
s += d[i]
if x > s {
return false
}
}
return true
})
if l > m {
return -1
}
return l
}
###ts
function minZeroArray(nums: number[], queries: number[][]): number {
const [n, m] = [nums.length, queries.length];
const d: number[] = Array(n + 1);
let [l, r] = [0, m + 1];
const check = (k: number): boolean => {
d.fill(0);
for (let i = 0; i < k; ++i) {
const [l, r, val] = queries[i];
d[l] += val;
d[r + 1] -= val;
}
for (let i = 0, s = 0; i < n; ++i) {
s += d[i];
if (nums[i] > s) {
return false;
}
}
return true;
};
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
###rust
impl Solution {
pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
let n = nums.len();
let m = queries.len();
let mut d: Vec<i64> = vec![0; n + 1];
let (mut l, mut r) = (0_usize, m + 1);
let check = |k: usize, d: &mut Vec<i64>| -> bool {
d.fill(0);
for i in 0..k {
let (l, r, val) = (
queries[i][0] as usize,
queries[i][1] as usize,
queries[i][2] as i64,
);
d[l] += val;
d[r + 1] -= val;
}
let mut s: i64 = 0;
for i in 0..n {
s += d[i];
if nums[i] as i64 > s {
return false;
}
}
true
};
while l < r {
let mid = (l + r) >> 1;
if check(mid, &mut d) {
r = mid;
} else {
l = mid + 1;
}
}
if l > m { -1 } else { l as i32 }
}
}
时间复杂度 $O((n + m) \times \log m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为数组 $\textit{nums}$ 和 $\textit{queries}$ 的长度。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
