标签： 线段树

3161.物块放置查询

目标

有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。

给你一个二维数组 queries ，它包含两种操作：

  1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。
  2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。

示例 1：

输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

示例 2：

输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。
查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

说明：

  • 1 <= queries.length <= 15 * 10^4
  • 2 <= queries[i].length <= 3
  • 1 <= queries[i][0] <= 2
  • 1 <= x, sz <= min(5 10^4, 3 queries.length)
  • 输入保证操作 1 中，x 处不会有障碍物。
  • 输入保证至少有一个操作类型 2 。

思路

代码

性能

2770.达到末尾下标所需的最大跳跃次数

目标

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

  • 0 <= i < j < n
  • -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

示例 1：

输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。

示例 2：

输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。

示例 3：

输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。

提示：

  • 2 <= nums.length == n <= 1000
  • -10^9 <= nums[i] <= 10^9
  • 0 <= target <= 2 * 10^9

思路

有一个数组 nums，对于小标 i 可以跳到 j > i && |nums[j] - nums[i]| <= target，返回从 0 跳到 n - 1 的最大跳跃次数。

定义 dp[i] 表示到达 i 的最大跳跃次数，dp[0] = 0，枚举 j ∈ [i + 1, n - 1] 如果 Math.abs(nums[j] - nums[i]) <= target 有 dp[j] = Math.max(dp[j], dp[i] + 1)，注意：如果 dp[i] == 0, i > 0，说明无法从 0 到达当前下标，直接跳过。

代码


/**
 * @date 2026-05-11 10:07
 */
public class MaximumJumps2770 {

    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && dp[i] == 0) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n - 1] == 0 ? -1 : dp[n - 1];
    }

}

性能

时间复杂度 O(n^2)，//todo 线段树维护最大值

3660.跳跃游戏IX

目标

给你一个整数数组 nums。

从任意下标 i 出发，你可以根据以下规则跳跃到另一个下标 j：

  • 仅当 nums[j] < nums[i] 时，才允许跳跃到下标 j，其中 j > i。
  • 仅当 nums[j] > nums[i] 时，才允许跳跃到下标 j，其中 j < i。

对于每个下标 i，找出从 i 出发且可以跳跃 任意 次，能够到达 nums 中的 最大值 是多少。

返回一个数组 ans，其中 ans[i] 是从下标 i 出发可以到达的最大值。

示例 1:

输入: nums = [2,1,3]
输出: [2,2,3]
解释:
对于 i = 0：没有跳跃方案可以获得更大的值。
对于 i = 1：跳到 j = 0，因为 nums[j] = 2 大于 nums[i]。
对于 i = 2：由于 nums[2] = 3 是 nums 中的最大值，没有跳跃方案可以获得更大的值。
因此，ans = [2, 2, 3]。

示例 2:

输入: nums = [2,3,1]
输出: [3,3,3]
解释:
对于 i = 0：向后跳到 j = 2，因为 nums[j] = 1 小于 nums[i] = 2，然后从 i = 2 跳到 j = 1，因为 nums[j] = 3 大于 nums[2]。
对于 i = 1：由于 nums[1] = 3 是 nums 中的最大值，没有跳跃方案可以获得更大的值。
对于 i = 2：跳到 j = 1，因为 nums[j] = 3 大于 nums[2] = 1。
因此，ans = [3, 3, 3]。

说明:

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

思路

有一个整数数组 nums，从任意下标 i 出发，可以向后跳到比 nums[i] 小的位置，向前跳到比 nums[i] 大的位置。返回从每一个下标 i 出发跳跃任意次能够到达的 nums 中的最大值。

定义 dp[i] 表示下标 i 所能到达的最大值，记录前缀最大值 preMax 与后缀最小值 suffixMin。如果 preMax[i + 1] <= suffixMin[i + 1]，dp[i] = preMax[i + 1]，否则 dp[i] = dp[i + 1]。

// todo: 树状数组 线段树 单调栈解法

代码


/**
 * @date 2026-05-07 14:41
 */
public class MaxValue3660 {

    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] preMax = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preMax[i + 1] = Math.max(preMax[i], nums[i]);
        }
        int suffixMin = nums[n - 1];
        dp[n - 1] = preMax[n];
        for (int i = n - 2; i >= 0; i--) {
            if (preMax[i + 1] <= suffixMin) {
                dp[i] = preMax[i + 1];
            } else {
                dp[i] = dp[i + 1];
            }
            suffixMin = Math.min(suffixMin, nums[i]);
        }
        return dp;
    }

}

性能

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;
    }

}

性能