标签： todo

3753.范围内总波动值II

目标

给你两个整数 num1 和 num2，表示一个 闭 区间 [num1, num2]。

一个数字的 波动值 定义为该数字中 峰 和 谷 的总数：

  • 如果一个数位 严格大于 其两个相邻数位，则该数位为 峰。
  • 如果一个数位 严格小于 其两个相邻数位，则该数位为 谷。
  • 数字的第一个和最后一个数位 不能 是峰或谷。
  • 任何少于 3 位的数字，其波动值均为 0。

返回范围 [num1, num2] 内所有数字的波动值之和。

示例 1：

输入： num1 = 120, num2 = 130
输出： 3
解释：
在范围 [120, 130] 内：
120：中间数位 2 是峰，波动值 = 1。
121：中间数位 2 是峰，波动值 = 1。
130：中间数位 3 是峰，波动值 = 1。
范围内所有其他数字的波动值均为 0。
因此，总波动值为 1 + 1 + 1 = 3。

示例 2：

输入： num1 = 198, num2 = 202
输出： 3
解释：
在范围 [198, 202] 内：
198：中间数位 9 是峰，波动值 = 1。
201：中间数位 0 是谷，波动值 = 1。
202：中间数位 0 是谷，波动值 = 1。
范围内所有其他数字的波动值均为 0。
因此，总波动值为 1 + 1 + 1 = 3。

示例 3：

输入： num1 = 4848, num2 = 4848
输出： 2
解释：
数字 4848：第二个数位 8 是峰，第三个数位 4 是谷，波动值为 2。

说明：

  • 1 <= num1 <= num2 <= 10^15

思路

代码

性能

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 。

思路

代码

性能

3093.最长公共后缀查询

目标

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
输出：[1,1,1]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

示例 2：

输入：wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
输出：[2,0,2]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = "gh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
对于 wordsQuery[1] = "acbfgh" ，只有下标为 0 的字符串有最长公共后缀 "fgh" 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
对于 wordsQuery[2] = "acbfegh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

说明：

  • 1 <= wordsContainer.length, wordsQuery.length <= 10^4
  • 1 <= wordsContainer[i].length <= 5 * 10^3
  • 1 <= wordsQuery[i].length <= 5 * 10^3
  • wordsContainer[i] 只包含小写英文字母。
  • wordsQuery[i] 只包含小写英文字母。
  • wordsContainer[i].length 的和至多为 5 * 10^5 。
  • wordsQuery[i].length 的和至多为 5 * 10^5 。

思路

// todo

代码

性能

1340.跳跃游戏V

目标

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

  • i + x ，其中 i + x < arr.length 且 0 < x <= d 。
  • i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

说明：

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length

思路

// todo

代码

性能

1665.完成所有任务的最少初始能量

目标

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

  • actuali 是完成第 i 个任务 需要耗费 的实际能量。
  • minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

说明：

  • 1 <= tasks.length <= 10^5
  • 1 <= actuali <= minimumi <= 10^4

思路

有一个二维数组 tasks，tasks[i] = [actuali, minimumi]，actuali 表示完成任务需要消耗的能量，minimumi 表示开始任务所需的最小能量。可以按任意顺序完成任务，求完成所有任务所需的最小初始能量。

//todo

代码

性能

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

}

性能

788.旋转数字

目标

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例：

输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

说明：

  • N 的取值范围是 [1, 10000]。

思路

判断 1 ~ N 的数字中，不含 3 4 7，且一定要含 2 5 6 9 的数字个数。

// todo:数位 dp

代码


/**
 * @date 2026-05-06 16:45
 */
public class RotatedDigits788 {

    public int rotatedDigits(int n) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        set.add(2);
        set.add(5);
        set.add(6);
        set.add(9);
        for (int i = 1; i <= n; i++) {
            int num = i;
            boolean valid = false;
            while (num > 0) {
                int d = num % 10;
                if (d == 3 || d == 4 || d == 7) {
                    break;
                }
                if (set.contains(d)){
                    valid = true;
                }
                num /= 10;
            }
            if (num == 0 && valid) {
                res++;
            }
        }
        return res;
    }
}

性能

3225.网格图操作后的最大分数

目标

给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。

如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。

请你返回执行任意次操作以后，最终网格图的 最大 总分数。

示例 1：

输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：11
解释：
第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。

示例 2：

输入：grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
输出：94
解释：
我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。

说明：

  • 1 <= n == grid.length <= 100
  • n == grid[i].length
  • 0 <= grid[i][j] <= 10^9

思路

代码

性能

3464.正方形上的点之间的最大距离

目标

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。

返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

示例 1：

输入： side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
输出： 2
解释：
选择所有四个点。

示例 2：

输入： side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
输出： 1
解释：
选择点 (0, 0) ，(2, 0) ，(2, 2) 和 (2, 1)。

示例 3：

输入： side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
输出： 1
解释：
选择点 (0, 0) ，(0, 1) ，(0, 2) ，(1, 2) 和 (2, 2)。

说明：

  • 1 <= side <= 10^9
  • 4 <= points.length <= min(4 side, 15 10^3)
  • points[i] == [xi, yi]
  • 输入产生方式如下：
    • points[i] 位于正方形的边界上。
    • 所有 points[i] 都 互不相同 。
  • 4 <= k <= min(25, points.length)

思路

代码

性能