【每日一题】2679. 矩阵中的和
问题描述
给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：
- 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
- 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。
请你返回最后的分数 。
示例 1：
1输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]] 2输出：15 3解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。示例 2：
1输入：nums = [[1]] 2输出：1 3解释：我们删除 1 并将分数增加 1 ，所以返回 1 。提示：
- 1 <= nums.length <= 300
- 1 <= nums[i].length <= 500
- 0 <= nums[i][j] <= 103
来源：力扣（LeetCode） 链接： https://leetcode.cn/problems/sum-in-a-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解决思路
使用堆
步骤
问题描述中提到 每一行选取最大的一个数，并删除它，自然地，可以选取堆来处理最大值的问题。
将输入的
m*n的数组转换为长度为m的列表，列表中的元素为长度为n的优先队列/最大堆。1// 处理输入，将输入转换为若干个堆 2List<Queue<Integer>> heapList = new ArrayList<>(); 3for (int[] row : nums) { 4 Queue<Integer> heap = new PriorityQueue<>(Integer::compareTo); 5 for (int num : row) { 6 heap.add(num); 7 } 8 heapList.add(heap); 9}依次弹出最大堆堆顶的元素，并比较这些取出的元素，选择其中最大的一个，计入分数。循环直至堆空。*由于这里的数组每一行元素的个数都相同，因此不用去计较具体哪一行的堆先空。
1int result = 0; 2// 处理堆，若堆不空则继续执行 3while (!heapList.get(0).isEmpty()) { 4 int max = 0; 5 // 遍历各个堆，选择最大的堆顶元素计入分数 6 for (Queue<Integer> heap : heapList) { 7 max = Math.max(max, heap.remove()); 8 } 9 result += max; 10}
复杂度分析
时间复杂度：$O(mn\log (n))$，遍历每一个元素共需 $O(mn)$ 的时间复杂度；优先队列每一次入队或出队需要 $\log (n)$ 的时间复杂度，一共 $m\times n$ 个元素，共需 $O(mn\log (n))$ 的时间复杂度。因此总共需要 $O(mn\log (n))$ 的时间复杂度。
空间复杂度：$O(mn)$，将输入的二维数组转换为堆的列表，需要和原数组一样大小的空间。
使用堆本质上是对输入内容的一个转换，然后根据题目描述去处理数据，并不需要什么太出彩的算法能力。
完整代码
1/*
2 由于每一轮需要选出一个最大的数从数组中移除，因此可以使用堆这种特殊的数据结构来达到目的
3 1. 将输入处理一下，放到若干个堆中
4 2. 遍历每一个堆，从中取出堆顶元素，比较它们的大小，选择最大的一个计入分数
5 */
6public int matrixSum(int[][] nums) {
7 // 处理输入，将输入转换为若干个堆
8 List<Queue<Integer>> heapList = new ArrayList<>();
9 for (int[] row : nums) {
10 Queue<Integer> heap = new PriorityQueue<>(Integer::compareTo);
11 for (int num : row) {
12 heap.add(num);
13 }
14 heapList.add(heap);
15 }
16
17 int result = 0;
18 // 处理堆，若堆不空则继续执行
19 while (!heapList.get(0).isEmpty()) {
20 int max = 0;
21 // 遍历各个堆，选择最大的堆顶元素计入分数
22 for (Queue<Integer> heap : heapList) {
23 max = Math.max(max, heap.remove());
24 }
25 result += max;
26 }
27 return result;
28}
使用排序
步骤
问题描述中提到 每一行选取最大的一个数……找到这些数字中最大的数字计入分数，也可以理解为依次比较每一行中第 $i$ 大的数字，并计入分数。
在第一轮，我们选取第 1 行中最大的数字 $a_{11}$、第 2 行中最大的数字 $a_{21}$、……、第 m 行中最大的数字 $a_{m1}$，移除这些数，并将它们的最大值 $\max{a_{i1}}$ 计入分数；
在第二轮我们选取第 1 行中最大的数字 $a_{12}$、第 2 行中最大的数字 $a_{22}$、……、第 m 行中最大的数字 $a_{m2}$，移除这些数，将它们的最大值 $\max{a_{i2}}$ 计入分数。明显地， $a_{12}$ 指的是原第 1 行中第二大的数字。
因此我们可以先对每一行进行排序，然后再选取每一列的最大值计入分数，就可以得到输出。
对输入的数组进行排序
1// 对输入的数组进行排序 2for (int[] ints : nums) { 3 Arrays.sort(ints); 4}依次遍历每一列，获取该列中最大的数计入分数
1// 依次遍历每一列，每次遍历选出各行第 i 大的元素 2for (int i = 0; i < nums[0].length; i++) { 3 int max = 0; 4 // 比较各行中第 i 大的元素，选出最大的一个计入分数 5 for (int[] num : nums) { 6 max = Math.max(max, num[i]); 7 } 8 result += max; 9}
复杂度分析
时间复杂度：$O(mn\log (n))$，Arrays.sort 默认实现是快速排序，时间复杂度为 $O(n\log n)$，共有 $m$ 个数组，排序总共需要 $O(mn\log (n))$ 的时间复杂度；遍历每一列，每次取出一列的元素比较出最大值，共 $n\times m$ 个元素，总共需要 $O(mn)$ 的时间复杂度；综上，总共需要 $O(mn\log (n))$ 的时间复杂度。
空间复杂度：$O(1)$，将输入的二维数组转换为堆的列表，需要和原数组一样大小的空间。
完整代码
1/*
2 选择每一行中最大的，然后比较各行的最大值，实际上是分别比较每一行第一大的数、第二大的数、直到第 n 大的数。
3 因此我们也可以先排序然后再按列进行比较，选出最大的数计入分数。
4 */
5public int matrixSum(int[][] nums) {
6 int result = 0;
7
8 // 对输入的数组进行排序
9 for (int[] ints : nums) {
10 Arrays.sort(ints);
11 }
12
13 // 依次遍历每一列，每次遍历选出各行第 i 大的元素
14 for (int i = 0; i < nums[0].length; i++) {
15 int max = 0;
16 // 比较各行中第 i 大的元素，选出最大的一个计入分数
17 for (int[] num : nums) {
18 max = Math.max(max, num[i]);
19 }
20 result += max;
21 }
22
23 return result;
24}