LeetCode --- 424周赛

题目列表

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]; // 维护 pre
            while(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) / 3
                d = 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 这种情况的 -1
                    updata(nums[i], nums[i], false);
                }
                pre_i = i;
            }
        }
        if(0 <= pre_i && pre_i < n - 1){
            // 对于 2 -1 -1 -1 这种情况的 -1
            updata(nums[pre_i], nums[pre_i], false);
        }
        return ans;
    }
};