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

难度困难

给你一个下标从 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 <= 10^5
1 <= m * n <= 10^5
-10^5 <= mat[i][j] <= 10^5

# 贪心 + 平衡树 + 记忆化搜索

对于元素 $(i,j)$ ，可以贪心的选择第 $i$ 行第一个比 $mat[i][j]$ 大的元素的所有下标，选择第 $j$ 列第一个比 $mat[i][j]$ 大的元素的所有下标。然后将该元素作为元素 $(i,j)$ 递归下去。

若 $mat[i][j] < x < y$ ，那么从 $mat[i][j]$ 到达 $y$ 需要经过 $x$ ，才可以使得答案更大

$\left[\begin{matrix}7 & 6 & 3\\-7 & -5 & 6 \\-7 & 0 &4\\6&6&0\\-8&6&0\end{matrix}\right]$

可以枚举每一个元素 $(i,j)$

对于 $(i,j)$ 左边的元素即： $mat[i][0\sim j - 1]$ 。可以使用有序集合平衡树升序保存 $mat[i][0\sim j-1]$ ，通过二分 $mat[i][j] + 1$ 可以查询到比 $mat[i][j]$ 大的最小元素
$(i,j)$ 右边的元素，上边的元素，下边的元素同理

可以使用 $map$ 保存每一行或者每一列的元素对应的下标集合

例如： $-7\longrightarrow (2,0),(3,0)$

	class Solution {
	Map<Integer, List<int[]>>[] mapr2;
	Map<Integer, List<int[]>>[] mapc2;

	public int maxIncreasingCells(int[][] mat) {
	n = mat.length;
	m = mat[0].length;
	mapr2 = new Map[n];
	mapc2 = new Map[m];

	for (int i = 0; i < n; i++) {
	// 上一个比它大的最小元素
	TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1 - o2);
	Map<Integer, List<int[]>> map;
	map = new HashMap<>();
	mapr2[i] = map;
	for (int j = 0; j < m; j++) {
	List<int[]> list = map.computeIfAbsent(mat[i][j], o -> new ArrayList<>());
	list.add(new int[]{i, j});

	Pair pair = new Pair(i, j);
	Integer v = set.ceiling(mat[i][j] + 1);
	if (v != null) {
	mapr.put(pair, v);
	}
	set.add(mat[i][j]);
	}
	// 下一个比它大的最小元素
	set.clear();
	for (int j = m - 1; j >= 0; j--) {
	Pair pair = new Pair(i, j);
	Integer v = set.ceiling(mat[i][j] + 1);
	if (v != null) {
	// 左右取较小者
	mapr.put(pair, Math.min(mapr.getOrDefault(pair, Integer.MAX_VALUE), v));
	}
	set.add(mat[i][j]);
	}
	}
	for (int j = 0; j < m; j++) {
	Map<Integer, List<int[]>> map;
	map = new HashMap<>();
	mapc2[j] = map;
	// 上一个比它大的最小元素
	TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1 - o2);
	for (int i = 0; i < n; i++) {
	List<int[]> list = map.computeIfAbsent(mat[i][j], o -> new ArrayList<>());
	list.add(new int[]{i, j});

	Pair pair = new Pair(i, j);
	Integer v = set.ceiling(mat[i][j] + 1);
	if (v != null) {
	mapc.put(pair, v);
	}
	set.add(mat[i][j]);
	}
	// 下一个比它大的最小元素
	set.clear();
	for (int i = n - 1; i >= 0; i--) {
	Pair pair = new Pair(i, j);
	Integer v = set.ceiling(mat[i][j] + 1);
	if (v != null) {
	// 上下取较小者
	mapc.put(pair, Math.min(mapc.getOrDefault(pair, Integer.MAX_VALUE), v));
	}
	set.add(mat[i][j]);
	}
	}
	memo = new int[n][m];
	int ans = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	ans = Math.max(ans, dfs(i, j));
	}
	}
	return ans;
	}

	int[][] memo;
	// 左右
	Map<Pair, Integer> mapr = new HashMap();
	// 上下
	Map<Pair, Integer> mapc = new HashMap();

	int n;
	int m;

	public int dfs(int i, int j) {
	if (memo[i][j] != 0) {
	return memo[i][j];
	}
	Map<Integer, List<int[]>> r = mapr2[i];
	Map<Integer, List<int[]>> c = mapc2[j];

	Pair pair1 = new Pair(i, j);
	int ans = 0;
	// 左右
	Integer v = mapr.get(pair1);
	if (v != null) {
	// 当前第 i 行
	List<int[]> list = r.get(v);
	if (list != null) {
	for (int[] ints : list) {
	ans = Math.max(ans, dfs(ints[0], ints[1]));
	}
	}
	}
	// 上下
	v = mapc.get(pair1);
	if (v != null) {
	// 当前第 i 列
	List<int[]> list = c.get(v);
	if (list != null) {
	for (int[] ints : list) {
	ans = Math.max(ans, dfs(ints[0], ints[1]));
	}
	}
	}
	return memo[i][j] = ans + 1;
	}
	}

	class Pair {
	int i;
	int j;

	public Pair(int i, int j) {
	this.i = i;
	this.j = j;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	Pair pair = (Pair) o;
	return i == pair.i && j == pair.j;
	}

	@Override
	public int hashCode() {
	return Objects.hash(i, j);
	}
	}

执行用时 $1828ms$ ，现在超时了

# 动态规划 + 排序优化

对于元素 $mat[i][j]$ 必然由 $i$ 行 $j$ 列中比它小的元素所转移而来

若枚举 $(i,0\sim j - 1)$ 的每个元素则会超时

设 $f[i][j]$ 为访问元素 $mat[i][j]$ 的最大数量，由于由 $i$ 行 $j$ 列中比它小的元素所转移而来，可以维护转移来源的最大值。

转移来源也只能是第 $i$ 行或者第 $j$ 列，所以可以使用数组维护最大值。

对矩阵中的元素进行排序并保存元素的所有位置，枚举排序后的元素

此时 $f[i][j] = max(rolMax[i],colMax[j]) + 1$

$rolMax[i]$ ：第 $i$ 行当前的最大值

$colMax[j]$ ：第 $j$ 行当前的最大值

此时遍历到 $mat[i][j]$ ，那么小于 $mat[i][j]$ 的元素必然已经遍历完成，即此时 $i$ 行 $j$ 列中比 $mat[i][j]$ 小的元素早已计算完成，所以此时 $rolMax[i]$ 与 $colMax[j]$ 就是第 $i$ 行与第 $j$ 列转移来源的最大值。

	class Solution {
	public int maxIncreasingCells(int[][] mat) {
	int n = mat.length;
	int m = mat[0].length;
	//[元素，下标集合]
	Map<Integer, List<int[]>> map = new TreeMap<>();
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	List<int[]> list = map.computeIfAbsent(mat[i][j], o -> new ArrayList<>());
	list.add(new int[]{i, j});
	}
	}
	int[] rowMax = new int[n];
	int[] colMax = new int[m];
	int ans = 0;
	// 按照元素大小遍历
	for (Integer v : map.keySet()) {
	// 元素对应的下标集合
	List<int[]> list = map.get(v);
	// 保存元素对应的最大值
	int[] mx = new int[list.size()];
	for (int i = 0; i < list.size(); i++) {
	int[] pos = list.get(i);
	mx[i] = Math.max(rowMax[pos[0]], colMax[pos[1]]) + 1;
	ans = Math.max(ans, mx[i]);
	}
	// 需要最后更新 rolMax [i], colMax [j], 防止一行或一列的重复元素相互影响
	// - 1, 7, 7
	// 若更新第一个 7 后直接更新 rolMax，
	// 那么第二个 7 则会由第一个 7 转移而来，错误
	for (int i = 0; i < list.size(); i++) {
	int[] pos = list.get(i);
	rowMax[pos[0]] = Math.max(mx[i], rowMax[pos[0]]);
	colMax[pos[1]] = Math.max(mx[i], colMax[pos[1]]);
	}
	}
	return ans;
	}
	}

有序集合贪心排序动态规划困难记忆化搜索

# 贪心 + 平衡树 + 记忆化搜索

# 动态规划 + 排序优化

使所有字符相等的最小成本

按公因数计算最大组件大小