use std::collections::HashMap;
impl Solution {
pub fn max_increasing_cells(mat: Vec<Vec<i32>>) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut mp: HashMap<i32, Vec<(usize, usize)>> = HashMap::new();
let mut row = vec![0; m];
let mut col = vec![0; n];
for i in 0..m {
for j in 0..n {
mp.entry(mat[i][j]).or_insert(Vec::new()).push((i, j));
}
}
let mut sorted_map: Vec<_> = mp.iter().collect();
sorted_map.sort_by(|a, b| a.0.cmp(b.0));
for (_, pos) in sorted_map {
let res: Vec<_> = pos.iter().map(|&(i, j)| row[i].max(col[j]) + 1).collect(); // 存放相同数值的答案，便于后续更新 row 和 col
for (&(i, j), &d) in pos.iter().zip(res.iter()) {
row[i] = row[i].max(d);
col[j] = col[j].max(d);
}
}
*row.iter().max().unwrap()
}
}
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 }
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;
}
}
'''
动态规划
f[i][j]表示到达mat[i][j]时所访问的单元格的最大数量
'''
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)) # 相同元素放在同一组，统计位置
ans = 0
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]
ans = max(ans, max(mx))
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 ans
