标签： 排序

目标

给你一个整数数组 nums 和一个整数 k。

你可以对数组中的每个元素 最多 执行 一次 以下操作：

• 将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2
输出： 6
解释：
对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1
输出： 3
解释：
对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

说明：

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

思路

有一个整数数组 nums，允许对数组中的每个元素加上 [-k, k] 的整数，求操作后数组中不同元素的最大个数。

先对数组进行排序，计算相同元素个数，同时记录前一个元素操作后的最大值 + 1，当前相同元素的个数可以操作变成不同元素的范围是 [Math.max(nums[start] - k, prev), Math.min(nums[start] + k, l + cnt - 1)]。

代码

/**
 * @date 2025-10-20 10:09
 */
public class MaxDistinctElements3397 {

    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        int i = 0;
        int prev = Integer.MIN_VALUE;
        int res = 0;
        Arrays.sort(nums);
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == nums[start]) {
                i++;
            }
            int cnt = i - start;
            int l = Math.max(nums[start] - k, prev);
            int r = Math.min(nums[start] + k, l + cnt - 1);
            res += r - l + 1;
            prev = r + 1;
        }
        return res;
    }

}

性能

目标

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

说明：

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

思路

有 n 个咒语 和 m 瓶药水，对于每一个咒语，如果它的强度 spells[i] 与 药水能量强度 potions[j] 的乘积 大于等于 success 称为一个成功的组合，返回每个咒语的成功组合数。

将药水按强度排序，二分查找最后一个不成功组合的下标，成功的组合数为 m - (index + 1)。

代码

/**
 * @date 2025-10-09 11:32
 */
public class SuccessfulPairs2300 {

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = potions.length;
        for (int i = 0; i < spells.length; i++) {
            int index = bs(potions, spells[i], success);
            spells[i] = n - 1 - index;
        }
        return spells;
    }

    public int bs(int[] potions, long spell, long success) {
        int r = potions.length - 1;
        int l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (spell * potions[m] >= success) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

说明:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路

有一个非负整数的数组，返回其中可以组成三角形的三元组。

可以先排序，然后使用二重循环，二分查找满足条件的第三边。

代码

/**
 * @date 2025-09-26 8:52
 */
public class TriangleNumber611 {

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = nums[i] + nums[j];
                int index = bs(nums, j, t);
                res += Math.max(0, index - j);
            }
        }
        return res;
    }

    public int bs(int[] nums, int l, int target) {
        int r = nums.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

• 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
• 右上角三角形 的对角线按 非递减顺序 排序。

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
解释：
标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：
[7, 2] 变为 [2, 7]。
[3] 保持不变。

示例 2：

输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。

说明：

• grid.length == grid[i].length == n
• 1 <= n <= 10
• -10^5 <= grid[i][j] <= 10^5

思路

参考 498.对角线遍历

代码

/**
 * @date 2025-08-28 8:57
 */
public class SortMatrix3446 {

    public int[][] sortMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int k = m + n - 1;
        for (int l = 1; l < n; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(null);
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        for (int l = n; l <= k; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(Collections.reverseOrder());
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        return grid;
    }
}

性能

目标

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。folder[j] 的子文件夹必须以 folder[j] 开头，后跟一个 "/"。例如，"/a/b" 是 "/a" 的一个子文件夹，但 "/b" 不是 "/a/b/c" 的一个子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

说明：

• 1 <= folder.length <= 4 * 10^4
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

思路

有一个文件夹列表，删除其中所有的子文件夹。

将文件夹列表排序，父目录总是会先出现，记为 prev，使用 startsWith 判断当前目录是否是子目录，如果不是更新 prev，并加入结果集合，否则直接跳过。需要注意 prev 需要以 / 结尾，否则会错误地匹配，比如 /a/b/c 并不是 /a/b/ca 的父目录。

也可以使用字典树来解决该问题，构造字典树，将最后一个节点标记为文件夹列表的下标，dfs 字典树，如果遇到标记非空则直接返回，不再查找子文件夹。

代码

/**
 * @date 2025-07-19 10:57
 */
public class RemoveSubfolders1233 {

    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        String prev = ".";
        List<String> res = new ArrayList<>();
        for (String path : folder) {
            if (path.startsWith(prev)) {
                continue;
            }
            res.add(path);
            prev = path + "/";
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

说明：

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

思路

有两个数组 arr1 与 arr2，如果 arr1[i] <= arr2[j]，则称 arr1[i] 与 arr2[j] 相匹配。arr1 中的元素最多只能匹配一个 arr2 中的元素，同时，arr2 中的元素最多只能匹配一个 arr1 中的元素，求最大匹配数。

贪心策略，arr1 中的最小元素优先匹配 arr2 中的最小元素。

代码

/**
 * @date 2025-07-13 20:20
 */
public class MatchPlayersAndTrainers2410 {

    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length;
        int n = trainers.length;
        int res = 0;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (players[i] <= trainers[j]) {
                res++;
                i++;
            }
            j++;
        }
        return res;
    }

}

性能

目标

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]
输出：2
解释：
第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]
输出：1
解释：
第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]
输出：0
解释：
所有工作日都安排了会议。

说明：

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

思路

在区间 [1, days] 上有一些区间 [si, ei]，求没有被这些区间覆盖的正整数个数。

将区间按起点排序，记录已访问区间的最大终点 prevEnd，si - prevEnd - 1 即为当前区间与上一个区间之间的整数个数。注意特殊处理开头与结尾。

网友题解则是合并相交的区间，用总数减去区间覆盖的整数即为答案。

代码

/**
 * @date 2025-07-11 18:53
 */
public class CountDays3169 {

    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        int res = 0;
        int prevEnd = 0;
        for (int[] meeting : meetings) {
            int interval = meeting[0] - prevEnd - 1;
            res += Math.max(interval, 0);
            prevEnd = Math.max(prevEnd, meeting[1]);
        }
        return res + Math.max(0, days - prevEnd);
    }

}

性能

目标

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。

同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。

请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

示例 1：

输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
  它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
  它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
  所以，答案为所有物品中的最大美丽值，为 6 。

示例 2：

输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
输出：[4]
解释：
每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。

示例 3：

输入：items = [[10,1000]], queries = [5]
输出：[0]
解释：
没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。

说明：

• 1 <= items.length, queries.length <= 10^5
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 10^9

思路

有一个二维数组 items，其元素 items[i] = [pricei, beautyi] 表示 item 的价格与美丽值。有一个查询数组，每一次查询的目标是找出价格小于等于 queries[i] 的物品中的最大美丽值。

为了求得答案，需要知道小于 queries[i] 都有哪些物品，然后从中找出最大美丽值。

先将 items 按照价格从小到大排序，二分查找 queries[i] 的上界下标 end。剩下的问题是找出 [0, end] 范围内的最大美丽值，这些值是固定的，可以预处理。

代码

/**
 * @date 2025-03-09 22:44
 */
public class MaximumBeauty2070 {

    public int[] maximumBeauty(int[][] items, int[] queries) {
        int n = items.length;
        Arrays.sort(items, (a, b) -> a[0] - b[0]);
        int[] maxBeauty = new int[n];
        maxBeauty[0] = items[0][1];
        for (int i = 1; i < n; i++) {
            maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int upperbound = bs(queries[i], items);
            if (upperbound >= 0 && upperbound < n) {
                res[i] = maxBeauty[upperbound];
            }
        }
        return res;
    }

    public int bs(int target, int[][] items) {
        int n = items.length;
        int left = 0, right = n - 1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (items[mid][0] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return right;
    }

}

性能