java 解法, 执行用时: 96 ms, 内存消耗: 55.6 MB, 提交时间: 2023-10-20 19:38:03

class Solution {
    public int[][] minScore(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] lines = new int[m];
        int[] cols = new int[n];
        List<int[]> items = new ArrayList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                items.add(new int[]{i,j});
            }
        }
        items.sort((a,b)->grid[a[0]][a[1]]-grid[b[0]][b[1]]);
        int[][] ans = new int[m][n];
        for(int []item:items){
            int x = item[0];
            int y = item[1];
            int v = Math.max(lines[x],cols[y])+1;
            ans[x][y] = v;
            lines[x] = v;
            cols[y] = v;
        }
        return ans;
    }
}

golang 解法, 执行用时: 228 ms, 内存消耗: 13.7 MB, 提交时间: 2023-10-20 19:37:31

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func minScore(grid [][]int) [][]int {
	var temp [][]int
	m, n := len(grid), len(grid[0])
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			temp = append(temp, []int{i, j})
		}
	}
	sort.Slice(temp, func(i, j int) bool {
		return grid[temp[i][0]][temp[i][1]] < grid[temp[j][0]][temp[j][1]]
	})
	maxCol, maxRow := make([]int, n), make([]int, m)
	for _, ints := range temp {
		i, j := ints[0], ints[1]
		grid[i][j] = max(maxCol[j], maxRow[i]) + 1
		maxRow[i] = grid[i][j]
		maxCol[j] = grid[i][j]
	}
	return grid
}

cpp 解法, 执行用时: 160 ms, 内存消耗: 45 MB, 提交时间: 2023-10-20 19:37:16

class Solution {
public:
    vector<vector<int>> minScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 将所有数字排序
        vector<tuple<int, int, int>> nums;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                nums.push_back(make_tuple(grid[r][c], r, c));
            }
        }
        sort(nums.begin(), nums.end());

        // 从最小的数字开始填入，每次更新当前行和列的最大值
        vector<int> row_max(m, 0);
        vector<int> col_max(n, 0);
        vector<vector<int>> ans(m, vector<int>(n, 0));
        for (auto &[num, r, c] : nums) {
            ans[r][c] = max(row_max[r], col_max[c]) + 1;
            row_max[r] = ans[r][c];
            col_max[c] = ans[r][c];
        }
        return ans;
    }
};

python3 解法, 执行用时: 328 ms, 内存消耗: 36.1 MB, 提交时间: 2023-10-20 19:36:59

class Solution:
    def minScore(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        # 将所有数字排序
        nums = []
        for r in range(m):
            for c in range(n):
                nums.append((grid[r][c], r, c))
        nums.sort()

        # 从最小的数字开始填入，每次更新当前行和列的最大值
        row_max = [0] * m
        col_max = [0] * n
        ans = [[0] * n for _ in range(m)]
        for num, r, c in nums:
            ans[r][c] = max(row_max[r], col_max[c]) + 1
            row_max[r] = ans[r][c]
            col_max[c] = ans[r][c]
        return ans
        

    def minScore2(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        hasr, hasc, nhas, ss = [0] * m, [0] * n, [[0] * n for _ in range(m)], sorted([grid[i][j],i,j] for i in range(m) for j in range(n))
        for v,i,j in ss: hasr[i] = hasc[j] = nhas[i][j] = max(hasr[i], hasc[j]) + 1
        return nhas