矩阵中的和
难度:
标签:
题目描述
You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:
- From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
- Identify the highest number amongst all those removed in step 1. Add that number to your score.
Return the final score.
Example 1:
Input: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]] Output: 15 Explanation: In the first operation, we remove 7, 6, 6, and 3. We then add 7 to our score. Next, we remove 2, 4, 5, and 2. We add 5 to our score. Lastly, we remove 1, 2, 3, and 1. We add 3 to our score. Thus, our final score is 7 + 5 + 3 = 15.
Example 2:
Input: nums = [[1]] Output: 1 Explanation: We remove 1 and add it to the answer. We return 1.
Constraints:
1 <= nums.length <= 3001 <= nums[i].length <= 5000 <= nums[i][j] <= 103
代码结果
运行时间: 74 ms, 内存: 32.9 MB
/*
题目思路：
1. 使用Java Stream处理每一行找到最大的元素并删除。
2. 在每轮操作中，收集所有被删除的元素，并找到这些元素中的最大值。
3. 将该最大值加入总分中。
4. 重复上述步骤直到矩阵为空。
*/
import java.util.*;
import java.util.stream.Collectors;
public class MatrixScoreStream {
public int maxScore(int[][] nums) {
int score = 0;
while (true) {
List<Integer> maxValues = Arrays.stream(nums)
.map(row -> {
OptionalInt maxOpt = Arrays.stream(row).max();
if (maxOpt.isPresent()) {
int max = maxOpt.getAsInt();
for (int j = 0; j < row.length; j++) {
if (row[j] == max) {
row[j] = Integer.MIN_VALUE; // 标记为删除
break;
}
}
return max;
} else {
return Integer.MIN_VALUE;
}
})
.filter(val -> val != Integer.MIN_VALUE)
.collect(Collectors.toList());
if (maxValues.isEmpty()) break; // 矩阵已空
score += Collections.max(maxValues);
}
return score;
}
public static void main(String[] args) {
MatrixScoreStream ms = new MatrixScoreStream();
int[][] nums1 = {{7,2,1},{6,4,2},{6,5,3},{3,2,1}};
int[][] nums2 = {{1}};
System.out.println(ms.maxScore(nums1)); // 输出: 15
System.out.println(ms.maxScore(nums2)); // 输出: 1
}
}
解释
方法:
题解的整体思路是首先将每一行的元素进行排序，确保每一行的最大元素位于行的末端。然后，按列遍历排序后的矩阵，每次遍历中，从每一行的当前列元素中找到最大值，累加到分数中。这种方法利用了排序后的行结构，每次从列中选取元素时，可以直接访问对应位置的元素，简化了每次查找行最大值的操作。
时间复杂度:
O(n * m log m)
空间复杂度:
O(n)
代码细节讲解
🦆
在这个算法中，为什么选择先对每一行进行排序？排序对最终的分数计算有什么影响？
▷🦆
算法中提到每次遍历列时，从每一行的当前列收集元素。这种方法是否能保证不会遗漏每行的最大值？
▷🦆
算法如何处理如果有多行具有相同的列最大值时的情况？
▷