删除每行中的最大值

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

• Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
• Add the maximum of deleted elements to the answer.

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

 

Example 1:

Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
The final answer = 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[10]]
Output: 10
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
The final answer = 10.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 100

/*
 * 思路：
 * 1. 使用stream对每一行进行处理，找到每一行的最大值并删除。
 * 2. 在每一步中，将所有最大值中的最大值加到答案中。
 */

import java.util.Arrays;
import java.util.Comparator;

public class SolutionStream {
    public int deleteGreatestValue(int[][] grid) {
        int totalSum = 0;
        while (Arrays.stream(grid).anyMatch(row -> row.length > 0)) {
            int maxInThisStep = Arrays.stream(grid)
                .filter(row -> row.length > 0)
                .mapToInt(row -> Arrays.stream(row).max().orElse(Integer.MIN_VALUE))
                .max()
                .orElse(Integer.MIN_VALUE);
            for (int[] row : grid) {
                if (row.length > 0) {
                    int maxVal = Arrays.stream(row).max().orElse(Integer.MIN_VALUE);
                    row = Arrays.stream(row).filter(num -> num != maxVal).toArray();
                }
            }
            totalSum += maxInThisStep;
        }
        return totalSum;
    }
}

题解的主要思路是首先对矩阵的每一行进行逆序排序，使得每行的最大元素都位于行的开始。然后，通过迭代每一列，收集每行的最大未被删除的元素，并累加这些最大值。具体步骤如下：1. 遍历矩阵的每一行，对每一行进行逆序排序。2. 初始化一个等长于行数的数组 a，用于暂存每一列中的最大值。3. 对于每一列，通过列迭代收集每一行对应位置的元素，找出这些元素中的最大值，并累加到结果 sum 中。4. 返回累加的结果 sum。

O(m * n log n)

O(m)