329. Max Rising Path

Longest Increasing Path in a Matrix

必学的矩阵DFS题型 大概就是像329号这题

要求找出最长的严格递增路径

限制是 站在每个点上企图延伸路径时

只能考虑东南西北任一方位 不能开斜线模式

当然 也不能跑离矩阵 因此边界管制是首要操作

轻松扫描全局答案

对于矩阵的每个元素matrix[i][j]

我们都要尝试由它为起点 寻找最长的递增路径长度

因此先开一个尺寸与matrix完全一致的maxRisingPath

初始化时 maxRisingPath所有元素都是-1 象徵着尚未访问过

然后对于每个matrix[i][j] 我们先看看四个 潜在 邻居：

1. matrix[i][j + 1] 向东
2. matrix[i + 1][j] 向南
3. matrix[i][j - 1] 向西
4. matrix[i - 1][j] 向北

轮到邻居$x$做边界检查时 一旦验证邻居$x$确实存在

那就能继续看 $x$的值是否比matrix[i][j]更大

更大的话 再来查 从$x$为起点的最长递增路径长度

拿来加1便是 从matrix[i][j]出发向$x$走时 能得到的最长递增路径长度

因此如果邻居$x$在maxRisingPath显示-1

说明$x$尚未被访问过 就得先拿DFS访问$x$

一旦$x$的最长递增路径长度定下来 假设叫$k$

我们就采取 $maxRisingPath[i][j] = max(maxRisingPath[i][j], 1 + k)$

的方针更新maxRisingPath[i][j]

在更新好maxRisingPath[i][j]后 别忘了和历史最大值比

时间和空间复杂度都是$O(mn)$ 其中$m$和$n$分别是矩阵的行数和列数

第329题虽然官方标记Hard 但其实不难 甚至偏简单 非常适合练基础功

C++

#include <algorithm>
#include <vector>
using namespace std;

class MaxRisingPath // LeetCode Q.329.
{
private:
    // An entry's max rising path value is -1 if this entry is unsearched.
    // Otherwise, max rising path value is the finalized value w.r.t. entry.
    vector<vector<int>> entries, maxRisingPath;

    int maxRisingLen = 1; // Base case.

    void dfsRisingPath(int rowIdx, int colIdx) {
        maxRisingPath[rowIdx][colIdx] = 1; // Base case: a path of only current entry.

        vector<pair<int, int>> neighbors = {
            {rowIdx + 1, colIdx}, // South.
            {rowIdx - 1, colIdx}, // North.
            {rowIdx, colIdx + 1}, // East.
            {rowIdx, colIdx - 1} // West.
        };

        for (const auto& [neighborRowIdx, neighborColIdx] : neighbors) {
            // Inbound checks on row & col indices.
            if (0 > neighborRowIdx || neighborRowIdx >= entries.size())
                continue;

            if (0 > neighborColIdx || neighborColIdx >= entries[0].size())
                continue;

            // Skip neighbors that aren't bigger than current entry.
            if (entries[rowIdx][colIdx] >= entries[neighborRowIdx][neighborColIdx])
                continue;

            if (maxRisingPath[neighborRowIdx][neighborColIdx] == -1) // Unsearched neighbor.
                dfsRisingPath(neighborRowIdx, neighborColIdx);

            int risingLen = 1 + maxRisingPath[neighborRowIdx][neighborColIdx];

            if (risingLen > maxRisingPath[rowIdx][colIdx])
                maxRisingPath[rowIdx][colIdx] = risingLen;

            if (risingLen > maxRisingLen)
                maxRisingLen = risingLen;
        }
    }

public:
    int findLongestRisingPath(vector<vector<int>>& matrix) {
        entries = matrix;

        maxRisingPath.assign(matrix.begin(), matrix.end()); // Base case.
        for (auto& row : maxRisingPath)
            fill(row.begin(), row.end(), -1);

        for (int rowIdx = 0; rowIdx < matrix.size(); rowIdx++) {
            for (int colIdx = 0; colIdx < matrix[0].size(); colIdx++) {
                if (maxRisingPath[rowIdx][colIdx] == -1)
                    dfsRisingPath(rowIdx, colIdx);
            }
        }

        return maxRisingLen;
    }
};

Python

class MaxRisingPath:  # LeetCode Q.329.
    def __init__(self):
        self.matrix = []
        self.max_rising_path = []
        self.max_rising_len = 1

    def find_longest_rising_path(self, matrix: list[list[int]]) -> int:
        self.matrix = matrix

        # An entry's max rising path value is -1 if this entry is unsearched.
        # Otherwise, max rising path value is the finalized value w.r.t. entry.
        self.max_rising_path = [[-1] * len(matrix[0]) for _ in range(len(matrix))]

        self.max_rising_len = 1  # Base case.

        for row_idx in range(len(matrix)):
            for col_idx in range(len(matrix[0])):
                if self.max_rising_path[row_idx][col_idx] == -1:
                    self._dfs_rising_path(row_idx, col_idx)

        return self.max_rising_len

    def _dfs_rising_path(self, row_idx: int, col_idx: int) -> None:
        self.max_rising_path[row_idx][col_idx] = 1  # Base case: a path of only current entry.

        neighbors: list[tuple[int, int]] = [
            (row_idx + 1, col_idx), (row_idx - 1, col_idx),  # South & North.
            (row_idx, col_idx + 1), (row_idx, col_idx - 1)  # East & West.
        ]

        for neighbor_row_idx, neighbor_col_idx in neighbors:
            # Inbound checks on row & col indices.
            if not (0 <= neighbor_row_idx < len(self.matrix)): continue

            if not (0 <= neighbor_col_idx < len(self.matrix[0])): continue

            # Only consider neighbors that are bigger than current entry.
            if self.matrix[row_idx][col_idx] < self.matrix[neighbor_row_idx][neighbor_col_idx]:
                # Unsearched neighbor.
                if self.max_rising_path[neighbor_row_idx][neighbor_col_idx] == -1:
                    self._dfs_rising_path(neighbor_row_idx, neighbor_col_idx)

                rising_len = 1 + self.max_rising_path[neighbor_row_idx][neighbor_col_idx]

                if rising_len > self.max_rising_path[row_idx][col_idx]:
                    self.max_rising_path[row_idx][col_idx] = rising_len

                if rising_len > self.max_rising_len: self.max_rising_len = rising_len