[Leetcode]329. Longest Increasing Path in a Matrix(C++)

题目描述

题目链接：329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

例子

例子 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].

例子 2

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

例子 3

Input: matrix = [[1]] Output: 1

Follow Up

Note

Constraints

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

0 <= matrix[i][j] <= 2^31 - 1

解题思路

这道题可以利用 DFS 结合记忆过程来求解，首先用等大的数组存储以每个位置为起点的最长上升路径的长度，初始为 0。然后遍历数组，对每一个位置，找到相邻且值比当前值大的位置作为下一个步候选位置递归的求解，返回该位置和长度。取四个方向中最长的长度并加 1 作为当前起点的长度。如果该位置的结果在之前的迭代中已经被求解并存储，则直接返回该结果即可。代码如下：

#include <vector>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        directions =
            std::vector<std::pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        max_lens = std::vector<std::vector<int>>(
            matrix.size(), std::vector<int>(matrix[0].size(), 0));

        int result = 1;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                result = std::max(result, dfs(matrix, i, j));
            }
        }

        return result;
    }

private:
    std::vector<std::pair<int, int>> directions;
    std::vector<std::vector<int>> max_lens;

    int dfs(const std::vector<std::vector<int>>& matrix, int row, int col) {
        if (max_lens[row][col] != 0) {
            return max_lens[row][col];
        }

        int len = 1;
        for (auto& dir : directions) {
            int r = row + dir.first;
            int c = col + dir.second;

            if (r < 0 || r >= matrix.size() || c < 0 || c >= matrix[0].size())
                continue;

            if (matrix[r][c] > matrix[row][col]) {
                len = std::max(len, 1 + dfs(matrix, r, c));
            }
        }

        max_lens[row][col] = len;

        return max_lens[row][col];
    }
};

时间复杂度: O(mn)
空间复杂度: O(mn)

GitHub 代码同步地址： 329.LongestIncreasingPathInAMatrix.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions