2713-矩阵中严格递增的单元格数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

**输入：** mat = [[3,1],[3,4]]
**输出：** 2
**解释：** 上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

示例 2：

**输入：** mat = [[1,1],[1,1]]
**输出：** 1
**解释：** 由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

示例 3：

**输入：** mat = [[3,1,6],[-9,5,7]]
**输出：** 4
**解释：** 上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • -105 <= mat[i][j] <= 105

请看 视频讲解 第四题，欢迎点赞！

提示 1

按元素值从小往大计算。

提示 2

定义 f[i][j] 表示到达 mat}[i][j] 时所访问的单元格的最大数量。那么答案就是所有 f[i][j] 的最大值。

如何计算 f[i][j]？从哪转移过来？

请注意，我们不需要知道具体从哪个单元格转移过来，只需要知道转移来源的 f 的最大值是多少。

提示 3

按照元素值从小往大计算，那么第 i 行的比 mat}[i][j] 小的 f 值都算出来了，大于等于 mat}[i][j] 的尚未计算，视作 0。

所以对于第 i 行，相当于取这一行的 f 值的最大值，作为转移来源的值。我们用一个长为 m 的数组 rowMax 维护每一行的 f 值的最大值。

对于每一列，也同理，用一个长为 n 的数组 colMax 维护。

所以有

f[i][j] = \max(\textit{rowMax}[i], \textit{colMax}[j]) + 1

这里加一是把 mat}[i][j] 算上。

细节

代码实现时 f[i][j] 可以省略，因为只需要每行每列的 f 值的最大值。

对于相同元素，在全部计算出最大值后，再更新到 rowMax 和 colMax 中。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        g = defaultdict(list)
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                g[x].append((i, j))  # 相同元素放在同一组，统计位置

        row_max = [0] * len(mat)
        col_max = [0] * len(mat[0])
        for _, pos in sorted(g.items(), key=lambda p: p[0]):
            # 先把最大值算出来，再更新 row_max 和 col_max
            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]
            for (i, j), f in zip(pos, mx):
                row_max[i] = max(row_max[i], f)  # 更新第 i 行的最大 f 值
                col_max[j] = max(col_max[j], f)  # 更新第 j 列的最大 f 值
        return max(row_max)
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxIncreasingCells(int[][] mat) {
        var g = new TreeMap<Integer, List<int[]>>();
        int m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                // 相同元素放在同一组，统计位置
                g.computeIfAbsent(mat[i][j], k -> new ArrayList<>()).add(new int[]{i, j});

        int ans = 0;
        int[] rowMax = new int[m], colMax = new int[n];
        for (var pos : g.values()) {
            var mx = new int[pos.size()];  // 先把最大值算出来，再更新 rowMax 和 colMax
            for (int i = 0; i < pos.size(); i++) {
                mx[i] = Math.max(rowMax[pos.get(i)[0]], colMax[pos.get(i)[1]]) + 1;
                ans = Math.max(ans, mx[i]);
            }
            for (int k = 0; k < pos.size(); k++) {
                int i = pos.get(k)[0], j = pos.get(k)[1];
                rowMax[i] = Math.max(rowMax[i], mx[k]); // 更新第 i 行的最大 f 值
                colMax[j] = Math.max(colMax[j], mx[k]); // 更新第 j 列的最大 f 值
            }
        }
        return ans;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxIncreasingCells(vector<vector<int>> &mat) {
        map<int, vector<pair<int, int>>> g;
        int m = mat.size(), n = mat[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                g[mat[i][j]].emplace_back(i, j); // 相同元素放在同一组，统计位置

        vector<int> row_max(m), col_max(n);
        for (auto &[_, pos]: g) {
            vector<int> mx; // 先把最大值算出来，再更新 row_max 和 col_max
            for (auto &[i, j]: pos)
                mx.push_back(max(row_max[i], col_max[j]) + 1);
            for (int k = 0; k < pos.size(); k++) {
                auto &[i, j] = pos[k];
                row_max[i] = max(row_max[i], mx[k]); // 更新第 i 行的最大 f 值
                col_max[j] = max(col_max[j], mx[k]); // 更新第 j 列的最大 f 值
            }
        }
        return *max_element(row_max.begin(), row_max.end());
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func maxIncreasingCells(mat [][]int) (ans int) {
	type pair struct{ x, y int }
	g := map[int][]pair{}
	for i, row := range mat {
		for j, x := range row {
			g[x] = append(g[x], pair{i, j}) // 相同元素放在同一组，统计位置
		}
	}
	a := make([]int, 0, len(g))
	for k := range g {
		a = append(a, k)
	}
	sort.Ints(a) // 从小到大

	rowMax := make([]int, len(mat))
	colMax := make([]int, len(mat[0]))
	for _, x := range a {
		pos := g[x]
		mx := make([]int, len(pos))
		for i, p := range pos {
			mx[i] = max(rowMax[p.x], colMax[p.y]) + 1 // 先把最大值算出来，再更新 rowMax 和 colMax
			ans = max(ans, mx[i])
		}
		for i, p := range pos {
			rowMax[p.x] = max(rowMax[p.x], mx[i]) // 更新第 p.x 行的最大 f 值
			colMax[p.y] = max(colMax[p.y], mx[i]) // 更新第 p.y 列的最大 f 值
		}
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn\log (mn))，其中 m 和 n 分别为 mat 的行数和列数。瓶颈在排序上。
  • 空间复杂度：\mathcal{O}(mn)。
 Comments
On this page
2713-矩阵中严格递增的单元格数
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 细节