标签： 线段树

1622.奇妙序列

目标

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类 ：

  • Fancy() 初始化一个空序列对象。
  • void append(val) 将整数 val 添加在序列末尾。
  • void addAll(inc) 将所有序列中的现有数值都增加 inc 。
  • void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
  • int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 109 + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

示例：

输入：
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：
Fancy fancy = new Fancy();
fancy.append(2);   // 奇妙序列：[2]
fancy.addAll(3);   // 奇妙序列：[2+3] -> [5]
fancy.append(7);   // 奇妙序列：[5, 7]
fancy.multAll(2);  // 奇妙序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 奇妙序列：[13, 17, 10]
fancy.multAll(2);  // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

说明：

  • 1 <= val, inc, m <= 100
  • 0 <= idx <= 10^5
  • 总共最多会有 10^5 次对 append，addAll，multAll 和 getIndex 的调用。

思路

代码

性能

3714.最长的平衡子串II

目标

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。

如果一个 子串 中所有 不同 字符出现的次数都 相同，则称该子串为 平衡 子串。

请返回 s 的 最长平衡子串 的 长度 。

子串 是字符串中连续的、非空 的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

  • 1 <= s.length <= 10^5
  • s 仅包含字符 'a'、'b' 和 'c'。

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由 a b c 三种字符组成的字符串，返回最长的平衡子串长度。

// todo

代码

性能

3721.最长平衡子数组II

目标

给你一个整数数组 nums。

如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。

返回 最长 平衡子数组的长度。

子数组 是数组中连续且 非空 的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

提示:

  • Store the first (or all) occurrences for each value in pos[val].
  • Build a lazy segment tree over start indices l in [0..n-1] that supports range add and can tell if any index has value 0 (keep mn/mx).
  • Use sign = +1 for odd values and sign = -1 for even values.
  • Initialize by adding each value's contribution with update(p, n-1, sign) where p is its current first occurrence.
  • Slide left l: pop pos[nums[l]], let next = next occurrence or n, do update(0, next-1, -sign), then query for any r >= l with value 0 and update ans = max(ans, r-l+1).

思路

// todo

代码

性能

3719.最长平衡子数组I

目标

给你一个整数数组 nums。

如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。

返回 最长 平衡子数组的长度。

子数组 是数组中连续且 非空 的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

  • 1 <= nums.length <= 1500
  • 1 <= nums[i] <= 10^5

思路

定义平衡子数组是 不同奇数元素个数 与 不同偶数元素个数 相等的子数组，求数组 nums 的平衡子数组的最大长度。

暴力解法是枚举所有可能的子数组，判断是否是平衡子数组，即子数组中不相同奇数个数与不相同偶数个数是否相等。

无需针对每一个子数组都重新计数，考虑使用两个哈希表分别记录奇数元素与偶数元素的出现次数，判断哈希表中的 key 的个数是否相等即可。注意针对每一个起点，需要重新初始化哈希表。

代码


/**
 * @date 2026-02-10 9:16
 */
public class LongestBalanced3719 {

    public int longestBalanced(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer>[] map = new HashMap[2];
            Arrays.setAll(map, x -> new HashMap<>());
            int l = nums[i] % 2;
            map[l].merge(nums[i], 1, Integer::sum);
            for (int j = i + 1; j < n; j++) {
                int r = nums[j] % 2;
                map[r].merge(nums[j], 1, Integer::sum);
                if (map[l].size() == map[l ^ 1].size()) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

}

性能

3454.分割正方形II

目标

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域只 统计一次 。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]
输出： 1.00000
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]
输出： 1.00000
解释：
由于蓝色正方形和红色正方形有重叠区域且重叠区域只统计一次。所以直线 y = 1 将正方形分割成两部分且面积相等。

说明：

  • 1 <= squares.length <= 5 * 10^4
  • squares[i] = [xi, yi, li]
  • squares[i].length == 3
  • 0 <= xi, yi <= 10^9
  • 1 <= li <= 10^
  • 所有正方形的总面积不超过 10^15。

思路

代码

性能

757.设置交集大小至少为2

目标

给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。

  • 例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。

返回包含集合可能的最小大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。

示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。

示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。

说明：

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= starti < endi <= 10^8

思路

定义包含集合是 与 intervals 中每个区间的交集大小至少为 2 的集合，求包含集合的最小 size。

根据 intervals 中每个区间的起点排序，倒序遍历区间，对于最后一个区间，显然优先选最左边的 2 个元素最优，将其按照从大到小顺序加入包含列表，接着访问下一个区间，判断包含集合的最小的两个元素是否在当前区间内：

  • 如果都在，直接跳过
  • 如果都不在，将当前区间左侧前两个元素按从大到小顺序加入包含列表
  • 如果只有一个在，需要比较当前区间左端点 l 与包含集合最小元素 min 的关系，如果 min > l 将 l 加入列表，否则（即 min == l，由于是按起点排序的，所以 min 不会小于 l），用 l + 1 替换原来的列表最后一个元素，然后将 l 加入列表

代码


/**
 * @date 2025-11-20 8:46
 */
public class IntersectionSizeTwo757 {

    public int intersectionSizeTwo(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<Integer> res = new ArrayList<>();
        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            if (p == 0 || res.get(p - 1) > r) {
                res.add(l + 1);
                res.add(l);
                p += 2;
            } else if (p > 1 && res.get(p - 2) > r) {
                if (res.get(p - 1) == l) {
                    res.set(p - 1, l + 1);
                }
                res.add(l);
                p++;
            }
        }
        return res.size();
    }

}

性能

3479.水果成篮III

目标

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

  • 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
  • 每个篮子只能装 一种 水果。
  • 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]
输出： 1
解释：
fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]
输出： 0
解释：
fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。

说明：

  • n == fruits.length == baskets.length
  • 1 <= n <= 10^5
  • 1 <= fruits[i], baskets[i] <= 10^9

思路

有水果 fruits 与 篮子 baskets 两个数组，fruits[i] 表示下标为 i 的水果数量，baskets[i] 表示下标为 i 位置上篮子的容量。现在需要按 fruits 的顺序从左往右将其放入篮子中，放置的位置是第一个能够容下水果的篮子，每个篮子只能放一种水果，如果没有位置能放下则保持未放置状态，求剩余未放置的水果种类。

暴力解法是枚举每种水果数量，然后枚举篮子，标记第一个能放下的篮子，时间复杂度为 O(n^2)。由于 basket 是无序的，没办法使用二分查找，并且排序会影响最终结果。因为未排序前，数量小的水果可能占据了大的篮子，导致数量多的水果无法放置。

考虑将 basket 分块，记录每一块的最大值，然后找到块内第一个大于 fruits[i] 的元素，然后将其置零。

代码


/**
 * @date 2025-08-05 15:20
 */
public class NumOfUnplacedFruits3479 {

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        int blockSize = (int) Math.ceil(Math.sqrt(n));
        int m = (int) Math.ceil((double) n / blockSize);
        int[] block = new int[m];
        int bi = 0;
        while (bi < m) {
            int start = bi * blockSize;
            int max = 0;
            for (int j = start; j < start + blockSize && j < n; j++) {
                max = Math.max(max, baskets[j]);
            }
            block[bi++] = max;
        }
        int res = n;
        for (int fruit : fruits) {
            int i = 0;
            for (; i < m; i++) {
                if (fruit <= block[i]) {
                    res--;
                    break;
                }
            }
            int start = i * blockSize;
            int newMax = 0;
            for (int j = start; j < start + blockSize && j < n; j++) {
                if (baskets[j] >= fruit) {
                    if (baskets[j] == block[i]) {
                        for (int k = j + 1; k < start + blockSize && k < n; k++) {
                            newMax = Math.max(newMax, baskets[k]);
                        }
                        block[i] = newMax;
                    }
                    baskets[j] = 0;
                    break;
                } else {
                    newMax = Math.max(newMax, baskets[j]);
                }
            }
        }
        return res;
    }

}

性能

3477.水果成篮II

目标

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

  • 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
  • 每个篮子只能装 一种 水果。
  • 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]
输出： 1
解释：
fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]
输出： 0
解释：
fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。

说明：

  • n == fruits.length == baskets.length
  • 1 <= n <= 100
  • 1 <= fruits[i], baskets[i] <= 1000

思路

有一个数组 baskets 和 fruits，从左到右遍历 fruits，并删除 baskets 中第一个大于等于 fruits[i] 的元素，返回 baskets 最后剩余元素个数。

依题意模拟。

代码


/**
 * @date 2025-08-05 9:10
 */
public class NumOfUnplacedFruits3477 {

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        int res = n;
        for (int fruit : fruits) {
            for (int i = 0; i < n; i++) {
                if (baskets[i] >= fruit){
                    res--;
                    baskets[i] = 0;
                    break;
                }
            }
        }
        return res;
    }

}

性能

3480.删除一个冲突对后最大子数组数目

目标

给你一个整数 n，表示一个包含从 1 到 n 按顺序排列的整数数组 nums。此外，给你一个二维数组 conflictingPairs，其中 conflictingPairs[i] = [a, b] 表示 a 和 b 形成一个冲突对。

从 conflictingPairs 中删除 恰好 一个元素。然后，计算数组 nums 中的非空子数组数量，这些子数组都不能同时包含任何剩余冲突对 [a, b] 中的 a 和 b。

返回删除 恰好 一个冲突对后可能得到的 最大 子数组数量。

子数组 是数组中一个连续的 非空 元素序列。

示例 1

输入： n = 4, conflictingPairs = [[2,3],[1,4]]
输出： 9
解释：
从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。
在 nums 中，存在 9 个子数组，其中 [1, 4] 不会一起出现。它们分别是 [1]，[2]，[3]，[4]，[1, 2]，[2, 3]，[3, 4]，[1, 2, 3] 和 [2, 3, 4]。
删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 9。

示例 2

输入： n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
输出： 12
解释：
从 conflictingPairs 中删除 [1, 2]。现在，conflictingPairs = [[2, 5], [3, 5]]。
在 nums 中，存在 12 个子数组，其中 [2, 5] 和 [3, 5] 不会同时出现。
删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 12。

说明：

  • 2 <= n <= 10^5
  • 1 <= conflictingPairs.length <= 2 * n
  • conflictingPairs[i].length == 2
  • 1 <= conflictingPairs[i][j] <= n
  • conflictingPairs[i][0] != conflictingPairs[i][1]

思路

代码

性能

3356.零数组变换II

目标

给你一个长度为 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;
    }

}

性能