标签： 排序

目标

你是一位系统管理员，手里有一份文件夹列表 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;
    }

}

性能

目标

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。

给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。

返回不含特殊楼层的 最大 连续楼层数。

示例 1：

输入：bottom = 2, top = 9, special = [4,6]
输出：3
解释：下面列出的是不含特殊楼层的连续楼层范围：
- (2, 3) ，楼层数为 2 。
- (5, 5) ，楼层数为 1 。
- (7, 9) ，楼层数为 3 。
因此，返回最大连续楼层数 3 。

示例 2：

输入：bottom = 6, top = 8, special = [7,6,8]
输出：0
解释：每层楼都被规划为特殊楼层，所以返回 0 。

说明：

• 1 <= special.length <= 10^5
• 1 <= bottom <= special[i] <= top <= 10^9
• special 中的所有值 互不相同

思路

给定一个区间 [bottom, top]，从中剔除一些整数，求最大的连续整数个数。

排序 special 数组计算相邻区间的最大值。注意 special 数组的元素都在区间范围内，可以直接处理首尾区间 special[i] - bottom 与 top - special[i]，然后再处理内部区间 special[i] - special[i - 1] - 1。

也可以将 bottom--，top++，然后统一处理。

代码

/**
 * @date 2025-01-06 8:42
 */
public class MaxConsecutive2274 {

    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        bottom--;
        top++;
        int res = 0;
        int n = special.length;
        int prev = bottom;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, special[i] - prev - 1);
            prev = special[i];
        }
        return Math.max(res, top - special[n - 1] - 1);
    }

}

性能

目标

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。

返回一个长度为 2 的列表 answer ：

• answer[0] 是所有 没有 输掉任何比赛的玩家列表。
• answer[1] 是所有恰好输掉 一场 比赛的玩家列表。

两个列表中的值都应该按 递增 顺序返回。

注意：

• 只考虑那些参与 至少一场 比赛的玩家。
• 生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：

输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。

示例 2：

输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。

说明：

• 1 <= matches.length <= 10^5
• matches[i].length == 2
• 1 <= winneri, loseri <= 10^5
• winneri != loseri
• 所有 matches[i] 互不相同

思路

给定一个记录比赛结果的二维数组，数组元素为[winneri, loseri]，求没有输掉任何比赛的玩家以及仅输掉一场比赛的玩家。

简单实现可以直接利用TreeSet保存返回结果，往里面放的时候先判断是否输掉过比赛，如果后面输掉了比赛还要将其从从没输掉比赛的集合中移除。

对于仅输掉一次比赛的集合，不能根据它来判断是否输掉过比赛，因为输掉两次会从集合中移除，如何后续还会输掉比赛，判断集合中没有，就会错误地向其中添加，因此需要额外记录输掉过比赛的集合。

官网题解使用的是哈希表记录失败的次数，效率更高。

代码

/**
 * @date 2024-05-22 9:03
 */
public class FindWinners2225 {

    public List<List<Integer>> findWinners(int[][] matches) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new TreeSet<>();
        Set<Integer> loseOnce = new TreeSet<>();
        Set<Integer> lost = new HashSet<>();
        for (int[] match : matches) {
            int win = match[0];
            int lose = match[1];
            neverLose.remove(lose);
            if (!lost.contains(win)) {
                neverLose.add(win);
            }
            if (!loseOnce.contains(lose) && !lost.contains(lose)) {
                loseOnce.add(lose);
            } else {
                loseOnce.remove(lose);
            }
            lost.add(lose);
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        List<Integer> loser = new ArrayList<>(loseOnce);
        res.add(winner);
        res.add(loser);
        return res;
    }

    public List<List<Integer>> findWinners_v1(int[][] matches) {
        Map<Integer, Integer> loseCnt = new HashMap<>(matches.length);
        for (int[] match : matches) {
            //可以直接在这里记录没有一次失败的
            loseCnt.merge(match[1], 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new HashSet<>();
        for (int[] match : matches) {
            if(!loseCnt.containsKey(match[0])){
                neverLose.add(match[0]);
            }
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        Collections.sort(winner);
        List<Integer> lostOnce = loseCnt.entrySet().stream()
                .filter((entry) -> entry.getValue() == 1)
                .map(Map.Entry::getKey).sorted()
                .collect(Collectors.toList());
        res.add(winner);
        res.add(lostOnce);
        return res;
    }
}

性能

暴力解

哈希加排序