目录
一，3354. 使数组元素等于零
二， 3355. 零数组变换 I
三，3356. 零数组变换 II
四，3357. 最小化相邻元素的最大差值
一，3354. 使数组元素等于零
本题实际上是一个前/后缀和的问题，就是判断前缀和与后缀和的值是否相同，如果相同且当前位置的值为0，说明往左走和往右走都可以，ans += 2；如果前缀和与后缀和的值差1，如果相同且当前位置的值为0，说明只能往左走/只能往右走，ans += 1。其他情况都不会使得nums中所有元素为0，直接返回 ans。
代码如下：
class Solution {public int countValidSelections(int[] nums) {int s = 0;for(int x : nums){s += x;}int pre = 0, cnt = 0;for(int x : nums){if(x > 0){pre += x;}else if(pre == s - pre){cnt += 2;}else if(Math.abs(pre*2-s) == 1){cnt += 1;}}return cnt;}
}二， 3355. 零数组变换 I
本题就是一道简单的差分题：
class Solution {public boolean isZeroArray(int[] nums, int[][] queries) {int n = nums.length;int[] arr = new int[n+1];for(int[] q : queries){int l = q[0], r = q[1];arr[l] -= 1;arr[r+1] += 1;}long s = 0;for(int i=0; i<n; i++){s += arr[i];if(s + nums[i] > 0) return false;}return true;}
}三，3356. 零数组变换 II
本题可以直接使用二分 + 差分：
class Solution {public int minZeroArray(int[] nums, int[][] queries) {int l = 0, r = queries.length;while(l <= r){int k = (l + r) / 2;if(check(nums, queries, k)){r = k - 1;}else{l = k + 1;}}return r+1 <= queries.length ? r+1 : -1;}boolean check(int[] nums, int[][] queries, int k){int n = nums.length;int[] diff = new int[n+1];for(int i=0; i<k; i++){int[] q = queries[i];int l = q[0], r = q[1], val = q[2];diff[l] -= val;diff[r+1] += val;}long s = 0;for(int i=0; i<n; i++){s += diff[i];if(s + nums[i] > 0) return false;}return true;}
}也可以使用双指针 + 差分，枚举nums数组，同时枚举执行 queries[k]，直到 nums[i] = 0，跳出里面循环，枚举下一个 nums[i]。
代码如下：
class Solution {public int minZeroArray(int[] nums, int[][] queries) {int n = nums.length;int[] diff = new int[n+1];int k = 0, sum = 0;for(int i=0; i<n; i++){int x = nums[i];sum += diff[i];while(k < queries.length && sum + x > 0){int[] q = queries[k];int l = q[0], r = q[1], val = q[2];diff[l] -= val;diff[r+1] += val;if(l <= i && i <= r){//满足 i 在 [L,R]sum -= val;}k++;}if(sum + x > 0) return -1; }return k;}
}四，3357. 最小化相邻元素的最大差值
如果两个数相邻没有-1，那么它们的绝对值差是固定的，可以直接计算；如果两个数相邻有-1，那么就需要进行分类讨论了（这里需要先算出与-1相邻的所有数中的最大值maxR和最小值minL，因为不管（x，y）取什么，都需要和这两值求绝对差）：
- 如果没有连续的 -1，对于 -1 左右的两个数 l 和 r （l <= r），它们的绝对差一定是 min((maxR - l+1) / 2，(r - minL+1) / 2)
- 如果有连续的 -1，对于连续 -1 左右的两个数 l 和 r （l <= r），它们的绝对差一定是 min((maxR - l + 1) / 2，(r - minL + 1) / 2，(maxR - maxL + 2) / 3)
- 这里忽略了一种情况，如果是前缀-1/后缀-1时，它只有一个数 x，它的绝对差是 min((maxR - x + 1) / 2，(x - minL + 1) / 2)
class Solution {public int minDifference(int[] nums) {int n = nums.length;int minL = Integer.MAX_VALUE;int maxR = 0;for(int i = 0; i < n; i++){if(nums[i] != -1 && (i > 0 && nums[i-1] == -1 ||i < n- 1 && nums[i+1] == -1)){minL = Math.min(minL, nums[i]);maxR = Math.max(maxR, nums[i]);}}int preI = -1;for(int i = 0; i < n; i++){if(nums[i] == -1) continue;if(preI >= 0){if(i - preI == 1){//相邻两个非0数的绝对差ans = Math.max(ans, Math.abs(nums[i] - nums[preI]));}else{// i - preI > 2:判断是否有连续的-1update(Math.min(nums[preI], nums[i]), Math.max(nums[preI], nums[i]), i - preI > 2, minL, maxR);}}else if(i > 0){//-1 -1 -1 2 的情况update(nums[i], nums[i], false, minL, maxR);}preI = i;}if(0 <= preI && preI < n - 1)// 2 -1 -1 -1 的情况update(nums[preI], nums[preI], false, minL, maxR);return ans;}private int ans;void update(int l, int r, boolean big, int minL, int maxR){int d = (Math.min(r-minL, maxR-l) + 1) / 2;if(big) {//如果有连续的-1，还需要和 (maxR - minL + 2) / 3 比较d = Math.min(d, (maxR - minL + 2) / 3);}ans = Math.max(ans, d);}
}
