第424场周赛：使数组元素等于零、零数组变换 Ⅰ、零数组变换 Ⅱ、最小化相邻元素的最大差值

Q1、使数组元素等于零

1、题目描述

给你一个整数数组 nums 。

开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动 方向 ：向左或者向右。

此后，你需要重复下面的过程：

• 如果 curr 超过范围 [0, n - 1] ，过程结束。
• 如果 nums[curr] == 0 ，沿当前方向继续移动：如果向右移，则 递增 curr ；如果向左移，则 递减 curr 。
• 如果 nums[curr] > 0:
  • 将 nums[curr] 减 1 。
  • 反转 移动方向（向左变向右，反之亦然）。
  • 沿新方向移动一步。

如果在结束整个过程后，nums 中的所有元素都变为 0 ，则认为选出的初始位置和移动方向 有效 。

返回可能的有效选择方案数目。

2、解题思路

1. 问题描述：

   • 从一个初始位置 curr 开始，选择方向（左或右），按题目要求依次处理元素。

   • 如果结束时 nums 所有元素为 0，则此方案有效。

   • 我们需要统计满足条件的方案数目。

2. 核心逻辑：

   • 遍历所有满足 nums[curr] == 0 的起始位置 curr。

   • 针对每个起始位置，尝试两种移动方向（左、右），模拟过程并验证是否满足条件。

   • 使用辅助数组 temp 保存当前模拟的状态，避免修改原始数组。

3. 模拟移动：

   • 如果当前位置值是 0，继续沿当前方向移动。

   • 如果当前位置值是 >0：

     • 减少当前值 1。
     • 反转方向。
     • 移动一步。

   • 如果当前位置越界（curr < 0 或 curr >= n），结束模拟。

4. 优化点：

   • 尽量减少不必要的模拟操作。

   • 当发现某个状态无法满足条件时立即终止。

3、代码实现

class Solution {
public:
    int countValidSelections(vector<int>& nums) {
        int n = nums.size();
        int result = 0;

        // 遍历所有可能的起始位置
        for (int start = 0; start < n; ++start) {
            if (nums[start] != 0) {
                continue;
            }

            // 两个方向: 1 表示向右, -1 表示向左
            for (int direction : {1, -1}) {
                vector<int> temp = nums; // 临时数组用于模拟
                int curr = start;
                bool valid = true;

                while (curr >= 0 && curr < n) {
                    if (temp[curr] == 0) {
                        // 当前位置为 0, 继续移动
                        curr += direction;
                    } else if (temp[curr] > 0) {
                        // 当前位置 > 0
                        temp[curr]--;           // 减少当前值
                        direction = -direction; // 反转方向
                        curr += direction;      // 移动一步
                    } else {
                        // 理论上不会出现这种情况
                        valid = false;
                        break;
                    }
                }

                // 如果数组所有元素变为 0, 则该方案有效
                if (valid && all_of(temp.begin(), temp.end(), [](int x) { return x == 0; })) {
                    result++;
                }
            }
        }

        return result;
    }
};

进阶方法

通过计算前后缀来计算。

假如左边和为2，右边和为2，此时，初始方向不管是向左还是向右都可以，+2；

假如左边和为2，右边和为3，此时，初始方向必须为向右，最后从左边离开边界，+1；

假如左边和为3，右边和为2，此时，初始方向必须为向左，最后从右边离开边界，+1；

假如左边和与右边和相差大于1，此时，初始方向不管是向左还是向右都没办法将数组归零。

class Solution {
public:
    int countValidSelections(vector<int>& nums) {
        int total = reduce(nums.begin(), nums.end());
        int ret = 0, pre = 0;
        for (const auto& num : nums) {
            if (num) {
                pre += num;
            } else if (pre * 2 == total) {
                ret += 2;
            } else if (abs(pre * 2 - total) == 1) {
                ret++;
            }
        }
        return ret;
    }
};

4、复杂度分析

• 时间复杂度：
  • 遍历所有起始位置 O(n)。
  • 每个起始位置模拟两种方向，最多访问每个元素一次，因此单次模拟的复杂度为 O(n)。
  • 总复杂度为 O(n²)。
• 空间复杂度：
  • 额外使用了一个数组 temp，大小为 O(n)。

Q2、零数组变换 Ⅰ

1、题目描述

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

• 在 nums 的下标范围 [li, ri] 内选择一个下标子集。
• 将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

数组的 子集 是对数组元素的选择（可能为空）。

2、解题思路

首先告诉大家，暴力过不了，超时了，打竞赛的时候第一反应还是首选暴力，最后浪费五分钟，下面是暴力代码

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();

        // 处理每个查询
        for (const auto& query : queries) {
            int left = query[0], right = query[1];
            while (left <= right) {
                nums[left++]--;
            }
        }

        // 验证
        for (const auto& num : nums) {
            if (num > 0) {
                return false;
            }
        }

        return true;
    }
};

暴力代码之所以超时，是因为在每个查询中，直接对范围 [left, right] 逐元素操作，时间复杂度为 O(q×k)，其中 q 是查询的数量，k 是区间长度的平均值。如何在暴力的基础上进行优化呢？

差分数组是一种高效处理区间操作的工具。通过将每次操作分摊到差分数组的起点和终点，避免了逐元素修改，从而极大地提高效率。

差分数组优化：

• 使用一个差分数组 diff 来快速记录区间的减操作：

  • 在 diff[left] 加上减操作的次数。

  • 在 diff[right + 1] 减去减操作的次数。

• 最终通过计算差分数组的前缀和，快速得到对每个位置的累积操作数。

验证零数组：

• 模拟操作时，将 nums[i] 减去当前累积操作数。

• 如果遍历完所有元素都满足条件，则返回 true。

3、代码实现

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);     // 差分数组, 大小为 n+1

        // 构建差分数组
        for (const auto& query : queries) {
            int left = query[0], right = query[1];
            diff[left] -= 1;            // 在左端点减 1
            if (right + 1 < n) {
                diff[right + 1] += 1;   // 在右端点的下一个位置加 1
            }
        }

        // 使用差分数组模拟操作
        int curr_op = 0; // 当前的操作累计值
        for (int i = 0; i < n; ++i) {
            curr_op += diff[i];         // 当前位置的操作累计
            nums[i] += curr_op;         // 应用累计操作到 nums[i]
            if (nums[i] < 0) {
                nums[i] = 0;            // 避免负值
            }
        }

        // 检查是否全部为零
        for (const auto& num : nums) {
            if (num != 0) {
                return false;
            }
        }

        return true;
    }
};

4、复杂度分析

时间复杂度：

• 构建差分数组：O(q)，其中 q 是 queries 的数量。
• 应用差分并验证：O(n)，其中 n 是 nums 的长度。
• 总复杂度：O(n+q)。

空间复杂度：

• 差分数组占用 O(n) 的额外空间。

Q3、零数组变换 Ⅱ

1、题目描述

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示在 nums 上执行以下操作：

• 将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。
• 每个下标的减少的数值可以独立选择。

零数组 是指所有元素都等于 0 的数组。

返回 k 可以取到的 最小非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。

2、解题思路

差分数组优化：

• 使用差分数组快速计算范围更新操作对原数组的影响，从而避免逐元素处理范围操作的高时间复杂度。

二分查找：

• 因为 k 是单调的（即处理更多查询一定能覆盖之前的效果），可以通过二分查找逐步缩小范围，找到最小满足条件的 k。

模拟操作：

• 对于一个固定的 k，使用差分数组和前缀和模拟查询操作的效果，并检查所有元素是否可以被减少到 0。

3、代码实现

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int m = queries.size();
        vector<int> diff(n + 1, 0);

        // 判断是否能通过前 k 个查询将 nums 变为零数组
        auto canMakeZero = [&](int k) -> bool {
            vector<int> curr_diff = diff;
            vector<int> curr_nums = nums;

            // 模拟前 k 个查询
            for (int i = 0; i < k; ++i) {
                int l = queries[i][0], r = queries[i][1], val = queries[i][2];
                curr_diff[l] -= val;
                if (r + 1 < n) {
                    curr_diff[r + 1] += val;
                }
            }

            // 应用差分数组到 curr_nums
            int running_sum = 0;
            for (int i = 0; i < n; ++i) {
                running_sum += curr_diff[i];
                curr_nums[i] += running_sum;
            }

            // 检查是否所有元素都 <= 0
            for (int i = 0; i < n; ++i) {
                if (curr_nums[i] > 0) {
                    return false;
                }
            }

            return true;
        };

        // 二分查找 k 的最小值
        int left = 0, right = m, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canMakeZero(mid)) {
                result = mid;
                // 尝试更小的 k
                right = mid - 1;
            } else {
                // 尝试更大的 k
                left = mid + 1;
            }
        }

        return result;
    }
};

4、复杂度分析

时间复杂度：

• 模拟操作：每次处理 O(n) 。
• 二分查找：最多执行O(logm) 次模拟操作。
• 总复杂度：O(n⋅logm) 。

空间复杂度：

• 差分数组和辅助数组：O(n)。
• 总复杂度：O(n)。

Q4、最小化相邻元素的最大差值

1、题目描述

给你一个整数数组 nums 。nums 中的一些值 缺失 了，缺失的元素标记为 -1 。

你需要选择 一个正 整数数对 (x, y) ，并将 nums 中每一个 缺失 元素用 x 或者 y 替换。

你的任务是替换 nums 中的所有缺失元素，最小化 替换后数组中相邻元素 绝对差值 的 最大值 。

请你返回上述要求下的 最小值 。

2、解题思路

为了解决这个问题，我们通过以下步骤：

1. 定位关键元素：
   • 找出所有非 -1 的元素。
   • 确定 -1 周围的最小和最大值，因为这些值决定了如何替换 -1 才能尽量减少相邻差值的最大值。
2. 设计更新规则：
   • 考虑到可能的替换组合，我们需要维护一个变量 max_diff 来记录替换后相邻元素的最大绝对差值。
   • 使用一个函数 updateMaxDiff 计算并更新替换后的最大差值，考虑以下情况：
     • 替换后的值与 -1 相邻的非 -1 元素之间的差值。
     • 存在多个连续的 -1 时，跨越空位的元素之间的差值。
3. 遍历数组：
   • 遍历数组，记录每个非 -1 元素的位置。
   • 根据相邻关系（是否紧邻或隔空位），更新 max_diff。
   • 处理边界情况，比如第一个和最后一个非 -1 元素。
4. 输出结果：
   • 遍历完成后，返回 max_diff，即替换后最小化的最大绝对差值。

3、代码实现

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();

        // 定义空位附近的最小值 min_adjacent 和最大值 max_adjacent
        int min_adjacent = INT_MAX, max_adjacent = 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))) {
                min_adjacent = min(min_adjacent, nums[i]);
                max_adjacent = max(max_adjacent, nums[i]);
            }
        }

        // 记录最终的最大差值
        int max_diff = 0;

        // 更新最大差值的函数
        auto updateMaxDiff = [&](int low, int high, bool considerTriple) {
            int candidate_diff = (min(high - min_adjacent, max_adjacent - low) + 1) / 2;
            if (considerTriple) {
                candidate_diff = min(candidate_diff, (max_adjacent - min_adjacent + 2) / 3);
            }
            max_diff = max(max_diff, candidate_diff);
        };

        int previous_index = -1; // 记录上一个非 -1 元素的位置

        // 遍历数组, 计算最大差值
        for (int i = 0; i < n; ++i) {
            if (nums[i] == -1) {
                continue;
            }

            if (previous_index >= 0) {
                // 如果当前元素和上一个非 -1 元素相邻
                if (i - previous_index == 1) {
                    max_diff = max(max_diff, abs(nums[i] - nums[previous_index]));
                } else {
                    // 如果不相邻, 计算跨越空位时的最大差值
                    updateMaxDiff(min(nums[previous_index], nums[i]), max(nums[previous_index], nums[i]), i - previous_index > 2);
                }
            } else if (i > 0) {
                // 如果这是第一个非 -1 元素且它不在开头
                updateMaxDiff(nums[i], nums[i], false);
            }
            // 更新上一个非 -1 元素的位置
            previous_index = i;
        }

        // 如果最后一个非 -1 元素靠近数组末尾
        if (0 <= previous_index && previous_index < n - 1) {
            updateMaxDiff(nums[previous_index], nums[previous_index], false);
        }

        return max_diff;
    }
};

4、复杂度分析

单次遍历数组，复杂度为 O(n)。