【LeetCode 题解】3356. 零数组变换 II 贪心差分与二分查找双解法

给定数组nums和查询列表queries，每个查询表示对区间[l, r]内的元素最多减少val（各元素减少量可独立选择）。要求找到最小的k，使得前k个查询处理后数组全为 0，若不存在则返回 - 1。

核心难点：如何高效计算区间累计减少量，确保每个位置的总减少量至少等于nums[i]。

java

public int minZeroArray(int nums, int queries) {int n = nums.length;int diff = new int[n + 1]; // 差分数组，长度n+1int cur = 0; // 当前累计减少量int k = 0; // 已使用的查询数for (int i = 0; i 二分查找k：在[0, queries.length]范围内二分查找最小可行的k。前缀和验证可行性：对于候选k，计算前k个查询的累计减少量（通过差分数组 + 前缀和），检查每个位置是否满足累计减少量 >= nums[i]。

java

public int minZeroArray(int nums, int queries) {int l = 0, r = queries.length;int ans = -1;while (l 解法时间复杂度空间复杂度贪心 + 差分O(n + m)O(n)二分 + 前缀和O((n + m) log m)O(n)贪心解法更优：线性遍历查询和数组，每个查询仅处理一次，适合大规模数据（如n, m ~ 1e5）。二分解法直观：适合需要验证的场景，但每次验证需遍历全数组，常数略高。

输入：nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

i=0（nums[0]=2）：cur=0（初始），不足 2，添加前两个查询：第一个查询：区间[0,2]加 1，diff[0]+=1，diff[3]-=1，i=0在区间内，cur+=1（变为 1）。第二个查询：区间[0,2]再加 1，diff[0]+=1，diff[3]-=1，i=0在区间内，cur+=1（变为 2）。k=2，cur=2 >= 2，满足。i=1（nums[1]=0）：cur += diff[1]（diff [1] 初始为 0），cur=2 >= 0，无需新增查询。i=2（nums[2]=2）：cur += diff[2]（diff [2] 初始为 0），cur=2 >= 2，满足。最终返回k=2，与示例一致。差分数组是区间更新的核心工具：将多次区间操作转化为端点修改，通过前缀和快速计算累计值。贪心解法更高效：逐元素处理 + 实时更新累计值，避免重复计算，适用于顺序处理问题。二分法适用于可行解判断：当问题具有单调性（前 k 个查询可行则 k+1 个必可行）时，可通过二分优化。

通过这两种解法，我们可以根据数据规模和问题特性选择最优方案，深入理解差分与前缀和的经典应用场景。