leetcode Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

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

Example 1:

nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

Return 4 The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1]]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

题目地址：leetcode Longest Increasing Path in a Matrix

题意：给定一个矩阵，在里面找出最大上升路径

方法一记忆化搜索

设dis[i][j]为当前点出发最大上升路径的值。初始设置为0，表示该点未知，需要更新。

再次碰到的时候只需要返回该值即可。

复杂度O(V + E)：V为顶点个数，E为边数，这里V为m*n，E为4*M*N，因此复杂度为O(mn)

C++

int dx[] = { 1 , -1, 0 , 0  };
int dy[] = { 0 , 0 , 1 , -1 };
class Solution {
public:
	int dfs(int x, int y, const int &m,const int &n,vector<vector<int>>& matrix, vector<vector<int>>& dis) {
		if (dis[x][y]) return dis[x][y];

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
				dis[x][y] = max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));
			}
		}
		return ++dis[x][y];
	}

	int longestIncreasingPath(vector<vector<int>>& matrix) {
		if (!matrix.size()) return 0;
		int m = matrix.size(), n = matrix[0].size();
		vector<vector<int> > dis(m, vector<int>(n, 0));
		int ans = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				ans = max(ans, dfs( i, j, m, n, matrix, dis));
			}
		}
		return ans;
	}
};

Java

public class Solution {
    int []dx = { 1 , -1, 0 , 0  };
    int []dy = { 0 , 0 , 1 , -1 };
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dis = new int [m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs( i, j, m, n, matrix, dis));
            }
        }
        return ans;
    }

    int dfs(int x, int y, int m,int n,int[][] matrix, int[][] dis) {
        if (dis[x][y] != 0) return dis[x][y];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
                dis[x][y] = Math.max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));
            }
        }
        return ++dis[x][y];
    }
}

Python

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])
        dis = [[0 for j in xrange(n)] for i in xrange(m)]
        return max([self.dfs(i, j, m, n, matrix, dis) for j in xrange(n) for i in xrange(m)])

    def dfs(self, x, y, m, n, matrix, dis):
        if dis[x][y]: return dis[x][y]
        for dx, dy in ([(1, 0), (-1, 0), (0, 1), (0, -1)]):
            nx, ny = x + dx, y + dy
            if nx >= 0 and nx < m and ny >= 0 and ny < n and matrix[x][y] < matrix[nx][ny]:
                dis[x][y] = max(dis[x][y], self.dfs(nx, ny, m, n, matrix, dis))
        dis[x][y] += 1
        return dis[x][y]

方法二拓扑排序

我们可以把矩阵看为一个图，[i, j]和[nx, ny]有链接当且仅当他们相邻且matrix[i][j] < matrix[nx][ny]，建立图之后进行拓扑排序，层数即为最长递增路径

复杂度O(mn)

class Solution {
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};

    int id(int i, int j, int col) const {
        return i * col + j;
    }

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        const int row = matrix.size();
        const int col = matrix[0].size();
        unordered_map<int, vector<int>> g;
        vector<int> in_degree(row * col, 0);
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && ny >= 0 && nx < matrix.size() && ny < matrix[0].size()
                            && matrix[nx][ny] > matrix[i][j]) {
                        g[id(i, j, col)].push_back(id(nx, ny, col));
                        in_degree[id(nx, ny, col)]++;
                    }
                }
            }
        }

        queue<int> q;
        for (int i = 0; i < in_degree.size(); ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
                
            }
        }

        int level = 0;
        while (!q.empty()) {
            int cur_size = q.size();
            for (int i = 0; i < cur_size; ++i) {
                int cur = q.front();
                q.pop();

                for (auto& next : g[cur]) {
                    if (--in_degree[next] == 0) {
                        q.push(next);
                    }
                }
            }
            ++level;
        }
        return level;
    }
};

本文是leetcode 329 Longest Increasing Path in a Matrix 的题解，更多题解可见

https://www.hrwhisper.me/leetcode-algorithm-solution/

leetcode Longest Increasing Path in a Matrix

方法一 记忆化搜索

方法二 拓扑排序

方法一记忆化搜索

方法二拓扑排序