Leetcode 2713. Maximum Strictly Increasing Cells in a Matrix

[Woodyiiiiiii]

2713. Maximum Strictly Increasing Cells in a Matrix

2713. Maximum Strictly Increasing Cells in a Matrix

类似题目：
2328. Number of Increasing Paths in a Grid
329. Longest Increasing Path in a Matrix
1632. Rank Transform of a Matrix

以前做过No.2328和No.329这种类型的题目，题目大概也是可以从任意节点出发，然后求最大严格递增路径或者个数(防止形成环状?)，做法一般有两种，要么直接从大到小DP或者多源BFS/优先队列。

那么回到这道题，这道题也是可以从各个点出发，但难点在于扩展到可以跳跃同一行/列。

应用多源BFS/优先队列的思想，本质上就是排序。

那么如何解决同一行/同一列跳跃？那就不考虑记录节点位置(i,j)了，只考虑记录行/列最值。这就是绕过问题抓住本质。

class Solution {
    public int maxIncreasingCells(int[][] mat) {
        TreeMap<Integer, List<int[]>> treeMap = new TreeMap<>();
        int m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; ++ i){
            for (int j = 0; j < n; ++ j){
                treeMap.putIfAbsent(mat[i][j], new ArrayList<>());
                treeMap.get(mat[i][j]).add(new int[]{i, j});
            }
        }
        int[] rowMax = new int[m], colMax = new int[n];
        int ans = 0;
        for (List<int[]> g : treeMap.values()) {
            int[] mx = new int[g.size()];
            for (int i = 0; i < g.size(); i++) {
                mx[i] = Math.max(rowMax[g.get(i)[0]], colMax[g.get(i)[1]]) + 1;
                ans = Math.max(ans, mx[i]);
            }
            for (int i = 0; i < g.size(); i++) {
                rowMax[g.get(i)[0]] = Math.max(rowMax[g.get(i)[0]], mx[i]);
                colMax[g.get(i)[1]] = Math.max(colMax[g.get(i)[1]], mx[i]);
            }
        }
        return ans;
    }
}

No.1632. Rank Transform of a Matrix也是类似的思路，但更复杂。