[每日一题] 2713.矩阵中严格递增的单元格数

博主： Richard
发布时间：2024 年 06 月 19 日
67 次浏览
暂无评论
1454字数
分类： LeetCode

> https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/description/?envType=daily-question&envId=2024-05-06

令 `dp[i][j]` 为移动到 `(i, j)` 的最大步数，那么 `dp[i][j]` 的值应该是从第 $i$ 行和第 $j$ 列中最大的 `dp` 值转移过来 (需要满足 `mat` 值小于 `mat[i][j]` ) 。

因此我们可以按照 `mat` 值进行排序，然后从小到大进行转移。因为 `dp[i][j]` 的取值只和行列的最大值有关，所以可以只维护每行和每列的最大 `dp` 值即可，因此状态转移方程如下：
$$
dp[i][j] = max(row[i], col[j]) + 1
$$

```c++
class Solution {
public:
    int maxIncreasingCells(std::vector<std::vector<int>>& mat) {
        const int m = mat.size(), n = mat[0].size();

std::map<int, std::vector<std::pair<int, int>>> graph;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                graph[mat[i][j]].emplace_back(i, j);
        }

std::vector<int> row_max(m), col_max(n);
        for (auto &[_, pos] : graph) {
            std::vector<int> max;
            for (auto &[i, j] : pos)
                max.push_back(std::max(row_max[i], col_max[j]) + 1);

for (int k = 0; k < pos.size(); k++) {
                auto &[i, j] = pos[k];
                row_max[i] = std::max(row_max[i], max[k]);
                col_max[j] = std::max(col_max[j], max[k]);
            }
        }

return *std::max_element(row_max.begin(), row_max.end());
    }
};
```

- 时间复杂度：$O(mn \cdot logmn)$ 。其中 $m$ 为 `mat` 的行数， $n$ 为 `mat` 的列数。主要消耗时间为最开始排序的消耗，需要 $O(mn \cdot logmn）$ 的时间复杂度。状态转移需要转移 $mn$ 次，每次需要 $O(1)$ 的时间复杂度，因此最终时间复杂度为 $O(mn \cdot logmn)$ 。
- 空间复杂度：$O(mn)$ 。

最后修改：2024 年 06 月 20 日