标签： hard

目标

给你一个 m x n 的二维整数数组 grid 和一个整数 k。你从左上角的单元格 (0, 0) 出发，目标是到达右下角的单元格 (m - 1, n - 1)。

有两种移动方式可用：

• 普通移动：你可以从当前单元格 (i, j) 向右或向下移动，即移动到 (i, j + 1)（右）或 (i + 1, j)（下）。成本为目标单元格的值。
• 传送：你可以从任意单元格 (i, j) 传送到任意满足 grid[x][y] <= grid[i][j] 的单元格 (x, y)；此移动的成本为 0。你最多可以传送 k 次。

返回从 (0, 0) 到达单元格 (m - 1, n - 1) 的 最小 总成本。

示例 1:

输入: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
输出: 7
解释:
我们最初在 (0, 0)，成本为 0。
当前位置    移动           新位置      总成本
(0, 0)    向下移动        (1, 0)     0 + 2 = 2
(1, 0)    向右移动        (1, 1)     2 + 5 = 7
(1, 1)    传送到(2, 2)    (2, 2)     7 + 0 = 7
到达右下角单元格的最小成本是 7。

示例 2:

输入: grid = [[1,2],[2,3],[3,4]], k = 1
输出: 9
解释:
我们最初在 (0, 0)，成本为 0。
当前位置    移动       新位置     总成本
(0, 0)    向下移动    (1, 0)    0 + 2 = 2
(1, 0)    向右移动    (1, 1)    2 + 3 = 5
(1, 1)    向下移动    (2, 1)    5 + 4 = 9
到达右下角单元格的最小成本是 9。

说明:

• 2 <= m, n <= 80
• m == grid.length
• n == grid[i].length
• 0 <= grid[i][j] <= 10^4
• 0 <= k <= 10

思路

有一个 m x n 的二维矩阵 grid，可以向右/向下移动，每次移动的成本为目标单元格的值。此外，在任意单元格 (i, j)，可以 零成本 传送到任意满足条件 (grid[x][y] <= grid[i][j]) 的单元格 (x, y)。求从 (0, 0) 出发最多传送 k 次到达 (m - 1, n - 1) 的最小成本。

定义 dp[i][j][t] 表示从 (0, 0) 最多传送 t 次到达 (i - 1, j - 1) 的最小成本。如果不传送，dp[i][j][t] = min(dp[i - 1][j][t], dp[i][j - 1][t]) + grid[i - 1][j - 1]，如果传送，需要找到所有元素值大于等于 grid[i - 1][j - 1] 的单元格 (x, y)，取 dp[x][y][t - 1] 的最小值。

代码

/**
 * @date 2026-01-28 10:04
 */
public class MinCost3651 {

    public int minCost(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] dp = new int[m + 1][n + 1][k + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[i][j], Integer.MAX_VALUE / 2);
            }
        }
        int maxCost = 0;
        for (int[] row : grid) {
            for (int cost : row) {
                maxCost = Math.max(maxCost, cost);
            }
        }
        int[] min = new int[maxCost + 1];
        Arrays.fill(min, Integer.MAX_VALUE);
        int[] suffixMin = new int[maxCost + 2];
        Arrays.fill(suffixMin, Integer.MAX_VALUE);
        for (int t = 0; t <= k; t++) {
            dp[0][1][t] = -grid[0][0];
            dp[1][0][t] = -grid[0][0];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    int cost = grid[i - 1][j - 1];
                    dp[i][j][t] = Math.min(Math.min(dp[i - 1][j][t], dp[i][j - 1][t]) + cost, suffixMin[cost]);
                    min[cost] = Math.min(min[cost], dp[i][j][t]);
                }
            }

            for (int i = maxCost; i >= 0; i--) {
                suffixMin[i] = Math.min(suffixMin[i + 1], min[i]);
            }
        }

        return dp[m][n][k];
    }

}

性能

目标

给你两个数组 nums1 和 nums2 。

请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

示例 1：

输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2：

输入：nums1 = [3,-2], nums2 = [2,-6,7]
输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3：

输入：nums1 = [-1,-1], nums2 = [1,1]
输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

说明：

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

思路

有两个数组 nums1 与 nums2，求这两个数组长度相等的子序列的点积的最大值。

定义 dp[i][j] 表示 nums1 的前 i 个元素的子序列与 nums2 的前 j 个元素的子序列的最大点积

• 如果选择 nums[i] * nums[j]，剩下的子问题变成 nums1 的前 i - 1 个元素的子序列 与 nums2 的前 j - 1 个元素的子序列的点积最大值，或者为 0，因为当前已经选择了，前面可以不选。即 Math.max(0, dp[i - 1][j - 1]) + nums[i] * nums[j]。
• 如果不选 nums[i] * nums[j]，问题变成 nums1 的前 i - 1 个元素的子序列 与 nums2 的前 j 个元素的子序列的点积最大值 dp[i - 1][j]，以及 dp[i][j - 1]、dp[i - 1][j - 1]。

代码

/**
 * @date 2026-01-08 9:05
 */
public class MaxDotProduct1458 {

    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[][] dp = new int[n1 + 1][n2 + 1];
        Arrays.fill(dp[0], Integer.MIN_VALUE);
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = Integer.MIN_VALUE;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                dp[i][j] = Math.max(Math.max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1], Math.max(dp[i - 1][j], dp[i][j - 1]));
            }
        }
        return dp[n1][n2];
    }
}

性能

目标

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

1. 每场会议都会在未占用且编号 最小 的会议室举办。
2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

说明：

• 1 <= n <= 100
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 10^5
• starti 的所有值 互不相同

思路

有 n 个会议室，编号为 0 ~ n - 1。有一个二维数组，meetings[i] 表示 [starti, endi) 范围内需要举办一场会议，会优先使用未被占用且编号最小的会议室。如果没有会议室可用，则需要延后举办，如果同一时间有多个会议需要举办，原开始时间最小的优先举办。

这个题目的关键点是，当有多个满足条件的会议室时，选择编号最小的，而不是最早可用的。需要使用两个优先队列，一个追踪会议室的最早空闲时间，另一个则追踪空闲会议室中编号最小的。将会议按照开始时间排序，按顺序遍历，将可选的会议室加入空闲编号堆，如果这个堆非空，从中取一个会议室，并将结束时间（可用时间）放入空闲时间堆中；否则，从空闲时间堆中取一个会议室，将其空闲时间加上会议持续时间后再放入堆中。

代码

/**
 * @date 2025-12-30 14:01
 */
public class MostBooked2402 {

    public int mostBooked(int n, int[][] meetings) {
        int[] cnt = new int[n];
        PriorityQueue<int[]> rooms = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; i++) {
            rooms.offer(new int[]{0, i});
        }
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        for (int[] meeting : meetings) {
            while (!rooms.isEmpty() && rooms.peek()[0] <= meeting[0]) {
                q.offer(rooms.poll());
            }
            int[] room;
            if (!q.isEmpty()) {
                room = q.poll();
                rooms.offer(new int[]{meeting[1], room[1]});
            } else {
                room = rooms.poll();
                rooms.offer(new int[]{room[0] + meeting[1] - meeting[0], room[1]});
            }
            cnt[room[1]]++;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[res]) {
                res = i;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

示例 1：

输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。

示例 2：

输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。

示例 3：

输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。

说明：

• 2 <= n <= 10^5
• 1 <= meetings.length <= 10^5
• meetings[i].length == 3
• 0 <= xi, yi <= n - 1
• xi != yi
• 1 <= timei <= 10^5
• 1 <= firstPerson <= n - 1

思路

按照时间将会议分组，按时间顺序遍历，使用并查集合并当天同一会议的专家，当所有会议遍历完成后，需要重置不知道秘密的连通块。

代码

/**
 * @date 2025-12-19 9:04
 */
public class FindAllPeople2092 {

    class UnionFind {
        private int[] fa;

        public UnionFind(int n) {
            this.fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public void reset(int a){
            fa[a] = a;
        }

        public int find(int a) {
            if (fa[a] != a) {
                fa[a] = find(fa[a]);
            }
            return fa[a];
        }

        public void merge(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x < y) {
                fa[y] = x;
            } else if (x > y) {
                fa[x] = y;
            }
        }

        public List<Integer> getConnected(int a) {
            int root = find(a);
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < fa.length; i++) {
                if (find(i) == root) {
                    res.add(i);
                }
            }
            return res;
        }
    }

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        UnionFind uf = new UnionFind(n);
        uf.merge(0, firstPerson);
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        for (int[] meeting : meetings) {
            map.putIfAbsent(meeting[2], new ArrayList<>());
            List<int[]> list = map.get(meeting[2]);
            list.add(meeting);
        }
        for (List<int[]> value : map.values()) {
            for (int[] meeting : value) {
                uf.merge(meeting[0], meeting[1]);
            }
            for (int[] meeting : value) {
                if (uf.find(meeting[0]) != 0){
                    uf.reset(meeting[0]);
                    uf.reset(meeting[1]);
                }
            }
        }
        return uf.getConnected(0);
    }

}

性能