标签： 差分数组

目标

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

说明：

• n == nums.length
• 2 <= n <= 10^5
• 1 <= nums[i] <= limit <= 10^5
• n 是偶数。

思路

有一个长度为偶数的数组 nums 和一个整数 limit，每次操作可以将任意元素替换为 [1, limit] 中的任意整数，求使得 nums 互补的最少操作次数。所谓互补指 nums[i] + nums[n - 1 - i] 的和都相等。

由于 1 <= nums[i] <= limit，每一对元素和都可以变成 [2, 2 * limit] 中的任意数字。

令 a = nums[i], b = nums[n - 1 - i], sum = a + b，如果只操作一次，考虑左侧 a -> 1 或者 b -> 1，sum 最多变化 max(a, b) - 1；右侧 a -> limit 或者 b -> limit，sum 最多变化 limit - min(a, b)。

• 将 sum 变成区间 [sum - (max(a, b) - 1), sum - 1], [sum + 1, sum + limit - min(a, b)] 内的值需要操作一次
• 变成 sum 的操作次数不变
• 其它 [2, sum - (max(a, b) - 1) - 1], [sum + limit - min(a, b) + 1, 2 * limit] 需要操作两次

使用差分数组来记录每对元素和变成目标和所需的操作次数，最后遍历所有目标和，取操作次数最小的即可。

代码

/**
 * @date 2026-05-13 10:13
 */
public class MinMoves1674 {

    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int max = 2 * limit;
        int[] diff = new int[max + 2];
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int sum = a + b;
            int l = sum - (Math.max(a, b) - 1);
            int r = sum + (limit - Math.min(a, b));
            diff[2] += 2;
            diff[Math.max(2, l)]--;
            diff[sum]--;
            diff[Math.min(sum + 1, max + 1)]++;
            diff[Math.min(r + 1, max + 1)]++;
        }
        int sum = 0, res = Integer.MAX_VALUE;
        for (int i = 2; i <= max; i++) {
            sum += diff[i];
            res = Math.min(sum, res);
        }
        return res;
    }

}

性能

目标

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

说明：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

思路

在第 1 天有一个人发现了一个秘密，每一个新知道秘密的人在 delay 天之后的 每一天 会向一个 新人 分享这个秘密，每一个人在知道秘密之后的 forget 天会忘记秘密，求第 n 天结束时知道秘密的人数。

定义 dp[i] 表示在第 i 天 新增 知道秘密的人数，它等于超过了延迟 delay 并且还没有忘记的人数总和，也即 [i - forget + 1, i - delay] 之间的新增人数总和，求和可以使用前缀和优化。

代码

/**
 * @date 2025-09-09 8:57
 */
public class PeopleAwareOfSecret2327 {

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int[] dp = new int[n + 1];
        int mod = 1000000007;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = Math.max(0, i - forget + 1); j <= Math.max(0, i - delay); j++) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
        int res = 0;
        for (int i = Math.max(0, n - forget + 1); i <= n; i++) {
            res = (res + dp[i]) % mod;
        }
        return res;
    }

}

性能

目标

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

每一个 queries[i] 表示对于 nums 的以下操作：

• 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
• 坐标范围内每一个元素减少的值相互 独立 。

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

请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。

示例 1：

输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
输出：1
解释：
删除 queries[2] 后，nums 仍然可以变为零数组。
对于 queries[0] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
对于 queries[1] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。

示例 2：

输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
输出：2
解释：
可以删除 queries[2] 和 queries[3] 。

示例 3：

输入：nums = [1,2,3,4], queries = [[0,3]]
输出：-1
解释：
nums 无法通过 queries 变成零数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= li <= ri < nums.length

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素减 1，返回最多可以删掉多少个操作，使得剩下的操作能够将数组中的所有元素变为 0。

对于元素 nums[0] 要将其变为 0 必须要操作 nums[0] 次，且操作范围必须包括 0，因此可以按照操作范围的左端点排序，每次选择右端点最远即覆盖最广的操作区间。可以维护一个由大到小的优先队列，从操作中选出左端点小于等于当前下标的操作，将其右端点放入队列。从队列中取出右端点大于等于当前下标的操作，使用差分数组进行区间修改。

代码

/**
 * @date 2025-05-22 23:02
 */
public class MaxRemoval3362 {

    public int maxRemoval(int[] nums, int[][] queries) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        Arrays.sort(queries, (a, b) -> a[0] - b[0]);
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        int num = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            while (k < queries.length && queries[k][0] <= i) {
                q.offer(queries[k++][1]);
            }
            while (!q.isEmpty() && q.peek() >= i && num > 0) {
                diff[q.poll() + 1]++;
                num--;
            }
            if (num > 0) {
                return -1;
            }
        }
        return q.size();
    }

}

性能

目标

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

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

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

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

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

示例 1：

输入： nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
输出： 2
解释：
对于 i = 0（l = 0, r = 2, val = 1）：
在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
数组将变为 [1, 0, 1]。
对于 i = 1（l = 0, r = 2, val = 1）：
在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
数组将变为 [0, 0, 0]，这是一个零数组。因此，k 的最小值为 2。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
输出： -1
解释：
对于 i = 0（l = 1, r = 3, val = 2）：
在下标 [1, 2, 3] 处分别减少 [2, 2, 1]。
数组将变为 [4, 1, 0, 0]。
对于 i = 1（l = 0, r = 2, val = 1）：
在下标 [0, 1, 2] 处分别减少 [1, 1, 0]。
数组将变为 [3, 0, 0, 0]，这不是一个零数组。

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 5 * 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 3
• 0 <= li <= ri < nums.length
• 1 <= vali <= 5

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素 最多 减去 vali = queries[2]，计算将数组中的所有元素变为 0 最少需要按顺序操作几次。

与 3355.零数组变换I 相比，求的是最小操作次数，每一次操作都需要判断数组元素是否全为 0，涉及到区间修改与区间查询，可以使用线段树维护区间最大值，每次操作后判断最大值是否大于 0。

官网给出了另一种思路，二分查找操作次数 k，针对每一个 k 问题变成 3355.零数组变换I。

代码

/**
 * @date 2025-05-21 9:35
 */
public class MinZeroArray3356 {

    public int minZeroArray(int[] nums, int[][] queries) {
        int right = queries.length - 1;
        int left = -1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums, mid, queries)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return left == queries.length ? -1 : left + 1;
    }

    public boolean check(int[] nums, int k, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        for (int i = 0; i <= k; i++) {
            int[] query = queries[i];
            int val = query[2];
            diff[query[0]] -= val;
            diff[query[1] + 1] += val;
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            if (num > 0) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

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

对于每个查询 queries[i]：

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

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

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

示例 1：

输入： nums = [1,0,1], queries = [[0,2]]
输出： true
解释：
对于 i = 0：
选择下标子集 [0, 2] 并将这些下标处的值减 1。
数组将变为 [0, 0, 0]，这是一个零数组。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]
输出： false
解释：
对于 i = 0： 
选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。
数组将变为 [4, 2, 1, 0]。
对于 i = 1：
选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。
数组将变为 [3, 1, 0, 0]，这不是一个零数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= li <= ri < nums.length

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素减 1，判断操作完成后能否将数组中的所有元素变为 0。

使用差分数组批量修改元素，最后判断是否存在元素大于 0 即可。

代码

/**
 * @date 2025-05-20 9:37
 */
public class IsZeroArray3355 {

    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        for (int[] query : queries) {
            diff[query[0]] -= 1;
            diff[query[1] + 1] += 1;
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            if (num > 0) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。

同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。

比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
[3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
[5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
[1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。

示例 1：

输入：differences = [1,-3,4], lower = 1, upper = 6
输出：2
解释：符合要求的隐藏数组为：
- [3, 4, 1, 5]
- [4, 5, 2, 6]
所以返回 2 。

示例 2：

输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
输出：4
解释：符合要求的隐藏数组为：
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
所以返回 4 。

示例 3：

输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。

说明：

• n == differences.length
• 1 <= n <= 10^5
• -10^5 <= differences[i] <= 10^5
• -10^5 <= lower <= upper <= 10^5

思路

已知某数组的差分数组 differences，以及数组元素值的上下界 lower upper，求有多少个满足条件的数组。

确定了第一个元素，后面整个数组就确定了。数组最大值与最小值的差是固定的，差值小于 upper - lower 就存在符合条件的数组，有 upper - lower - (max - min) + 1 个。注意求 max 与 min 时数据可能溢出，使用 long 类型。

代码

/**
 * @date 2025-04-21 0:19
 */
public class NumberOfArrays2145 {

    public int numberOfArrays(int[] differences, int lower, int upper) {
        int n = differences.length;
        long max = 0;
        long min = 0;
        long val = 0;
        for (int i = 0; i < n; i++) {
            val += differences[i];
            max = Math.max(max, val);
            min = Math.min(min, val);
        }
        long res = upper - lower - (max - min) + 1;
        return (int) Math.max(res, 0);
    }

}

性能

目标

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]
解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

说明：

• 0 <= startTime < endTime <= 10^9
• 每个测试用例，调用 book 函数最多不超过 400次

思路

参考 731.我的日程安排表II，同样的思路，只不过求得是相交区间数量的最大值。

代码

/**
 * @date 2025-01-04 15:40
 */
public class MyCalendarThree {

    TreeMap<Integer, Integer> cnt = new TreeMap<>();

    public MyCalendarThree() {

    }

    public int book(int startTime, int endTime) {
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1);
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1);
        int res = 0;
        int appearanceCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int value = entry.getValue();
            appearanceCnt += value;
            res = Math.max(appearanceCnt, res);
        }
        return res;
    }
}

性能