🔗 🔴 2713. Maximum Strictly Increasing Cells in a Matrix 2387

tags: `Weekly Contest 347` `矩陣(Matrix)` `動態規劃(DP)` `雜湊表(Hash Table)` `排序(Sorting)`

題意

給定一個大小為 $m \times n$ 的矩陣 $\text{mat}$ ，你可以選擇任意一個儲存格作為起始點。

從起始點開始，你可以移動到 同一橫列或同一直行中 的任何其他位置，但只有當目標位置的值 嚴格大於 當前位置的值時才能進行移動。你可以重複這個過程，從一個位置移動到另一個位置，直到無法再進行任何移動為止。

找出從某個位置開始，可以訪問的最大儲存格數量。

約束條件

$m = \text{mat.length}$
$n = \text{mat[i].length}$
$1 \leq m, n \leq 10^5$
$1 \leq m \times n \leq 10^5$
$-10^5 \leq \text{mat}[i][j] \leq 10^5$

思路：動態規劃(DP) + 雜湊表(Hash Table) + 排序(Sorting)

由於只有當目標位置的值 嚴格大於 當前位置的值時才能進行移動，因此對於任意位置 $(i, j)$ ，其轉移來源的值必須 嚴格小於 $\text{mat}[i][j]$ 。

故可以將值與位置的對應關係存入雜湊表(Hash Table) ，並對雜湊表的鍵值進行排序(Sorting) ，從小到大進行遍歷，確保轉移來源的值小於目標位置的值。

令 $f[i][j]$ 表示最後的位置在 $(i, j)$ 時，可以訪問的最大嚴格遞增序列的長度。但由於轉移可以發生在同一橫列或同一直行中，因此只需要分別維護最後在每一橫列和每一直行的最大嚴格遞增序列的長度即可。

令 $\text{row\_max}[i]$ 表示最後在第 $i$ 橫列的最大嚴格遞增序列的長度， $\text{col\_max}[j]$ 表示最後在第 $j$ 直行的最大嚴格遞增序列的長度，兩者皆初始化為 $0$ 。轉移時，對於每個位置 $(i, j)$ ，其最大嚴格遞增序列的長度為 $\max(\text{row\_max}[i], \text{col\_max}[j]) + 1$ 。最後取 $\max(\text{row\_max})$ 或 $\max(\text{col\_max})$ 皆可。

但同一個值可能出現在多個位置，因此在計算轉移結果時，需要先將所有位置的結果計算出來，再進行更新，以免被覆蓋，即發生轉移來源和當前位置的值相同的情況。或是先備份 $\text{row\_max}$ 和 $\text{col\_max}$ ，再進行更新，但這樣在最壞情況下需要 $\mathcal{O}(mn (n + m))$ 的時間來處理備份，在本題中會超時。

複雜度分析

時間複雜度： $\mathcal{O}((mn) \log (mn))$ $O ((mn) lo g (mn))$ ，其中 $m$ $m$ 和 $n$ $n$ 分別是矩陣的行數和列數。
- 遍歷矩陣，將所有位置以及其數字存入雜湊表的時間複雜度為 $\mathcal{O}(mn)$ 。
- 排序雜湊表的時間複雜度為 $\mathcal{O}((mn) \log (mn))$ 。
- 計算轉移結果的時間複雜度為 $\mathcal{O}(mn)$ 。
空間複雜度： $\mathcal{O}(mn)$

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        g = defaultdict(list)
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                g[x].append((i, j))
        row_max, col_max = [0] * m, [0] * n
        for x, pos in sorted(g.items(), key = lambda x: x[0]):
            # 要先把轉移的結果算出來，否則會被覆蓋
            res = [max(row_max[i], col_max[j]) + 1 for i, j in pos]
            for (i, j), r in zip(pos, res):
                row_max[i] = max(row_max[i], r)
                col_max[j] = max(col_max[j], r)
        return max(row_max) # or return max(col_max)

class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        map<int, vector<pair<int, int>>> g;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                g[mat[i][j]].push_back({i, j});
            }
        }
        vector<int> row_max(m, 0), col_max(n, 0);
        for (auto& kv : g) {
            auto& pos = kv.second;
            vector<int> res; // 要先把轉移的結果算出來，否則會被覆蓋
            for (auto& ij : pos) {
                int i = ij.first, j = ij.second;
                res.push_back(max(row_max[i], col_max[j]) + 1);
            }
            for (int k = 0; k < pos.size(); k++) {
                int i = pos[k].first, j = pos[k].second;
                row_max[i] = max(row_max[i], res[k]);
                col_max[j] = max(col_max[j], res[k]);
            }
        }
        return *max_element(row_max.begin(), row_max.end());
    }
};