题目列表
3354. 使数组元素等于零
3355. 零数组变换 I
3356. 零数组变换 II
3357. 最小化相邻元素的最大差值
一、使数组元素等于零
这题的本质就是看 nums[i] = 0 的左右两边的子数组和是否相等 / 相差为1，当两边的和相等时，先向左或者先向右都能让整个数组为0，当两边的和相差为1时，先向和较大的一边进行移动，才能让整个数组为0 【如果不太明白建议手动模拟一下】，代码如下
class Solution {
public:int countValidSelections(vector<int>& nums) {int n = nums.size();int suf = accumulate(nums.begin(), nums.end(), 0);int pre = 0, ans = 0;for(int i = 0; i < n; i++){ // 分别计算前缀和 / 后缀和if(nums[i] == 0){if(pre == suf) ans += 2;else if(abs(pre - suf) == 1) ans++;}pre += nums[i];suf -= nums[i];}return ans;}
};二、零数组变换I
这题的query涉及对区间进行加减操作，很适合用差分数组来做(可以在O(n)的时间内实现对区间的+/-操作)，代码如下
class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& q) {int n = nums.size(), m = q.size();vector<int> diff(n + 1);for(auto v: q){diff[v[0]]--;diff[v[1]+1]++;}int pre = 0;for(int i = 0; i < n; i++){pre += diff[i];if(pre + nums[i] > 0)return false;}return true;}
};三、零数组变换II
这题作为第二题的进阶，问我们最少顺序执行多少次query，才能让整个数组为0，该问题满足二分条件，我们可以复用第二题的代码作为check函数，代码如下
class Solution {using LL = long long;
public:int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size(), m = queries.size();auto check = [&](int k)->bool{vector<LL> diff(n + 1);for(int i = 0; i < k; i++){auto v = queries[i];diff[v[0]] -= v[2]; // 注意这里是 -v[2]，不是 -1，在拷贝第二题代码的时候要注意diff[v[1]+1] += v[2];}LL pre = 0;for(int i = 0; i < n; i++){pre += diff[i];if(pre + nums[i] > 0)return false;}return true; };int l = 0, r = m;while(l <= r){int mid = l + (r - l)/2;if(check(mid)) r = mid - 1;else l = mid + 1;}return l == m + 1 ? -1 : l;}
};这里还有另外一个思路：我们可以边遍历数组，边处理query，即同时维护差分数组和当前元素的操作数(这里操作数表示当前这么多次query后，nums[i]应该被减去的值)，具体代码如下
class Solution {
public:int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size(), m = queries.size();vector<int> diff(n + 1);int j = 0, pre = 0;for(int i = 0; i < n; i++){pre += diff[i]; // 维护 prewhile(pre < nums[i] && j < m){int l = queries[j][0], r = queries[j][1], val = queries[j][2];j++;diff[l] += val;diff[r+1] -= val;if(l <= i && i <= r) // 在这种情况下 pre += diff[i] 无法被执行，所以我们直接修改 pre 即可pre += val;}if(pre < nums[i]) return -1; // 表示所有query都执行了，也不能让 nums[i] = 0}return j;}
};四、最小化相邻元素的最大差值
思路如下
class Solution {
public:int minDifference(vector<int>& nums) {int n = nums.size();int left = INT_MAX, right = INT_MIN;for(int i = 0; i < n; i++){if(nums[i] > 0 && (i && nums[i-1] == -1 || i + 1 < n && nums[i+1] == -1)){left = min(left, nums[i]);right = max(right, nums[i]);}}int ans = 0;auto updata = [&](int L, int R, bool islimit){// 考虑将 -1 划分到 [left, R] 还是 [L, right] 中int d = (min(right - L, R - left) + 1) / 2;if(islimit) { // 考虑连续的 -1 的情况，d 的上限为 (right - left + 2) / 3d = min(d, (right - left + 2) / 3);}ans = max(ans, d);};int pre_i = -1;for(int i = 0; i < n; i++){if(nums[i] > 0){if(pre_i >= 0){if(i - pre_i == 1){ // 两个连续的 > 0 的数ans = max(ans, abs(nums[i] - nums[pre_i])); // 跟新答案}else{updata(min(nums[i], nums[pre_i]), max(nums[i], nums[pre_i]), i - pre_i > 2); // i - pre_i > 2 用来判断是否有连续的 -1}}else if(i > 0){// 对于 -1 -1 -1 2 这种情况的 -1updata(nums[i], nums[i], false);}pre_i = i;}}if(0 <= pre_i && pre_i < n - 1){// 对于 2 -1 -1 -1 这种情况的 -1updata(nums[pre_i], nums[pre_i], false);}return ans;}
};