题目
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.Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.Subscribe to see which companies asked this question
Show Tags
题目大意：给出一个矩阵，求矩阵中最大增序列的长度。
简单的思路
这道题可以看作一个四叉树的深度优先搜索。
为什么题目中的矩阵可以看作四叉树？因为两个相邻元素，只有大小不相等时，才会有一条边，从大的元素指向小的元素。这样连接之后不可能出现环，因为若有环存在，说明有a>b>…>a，显然不成立。连接完所有的边之后，以最小元素为根，上下左右四个邻居为子结点，形成了一颗四叉树。
想要求最大递增序列，就是从根节点到最深的叶子结点，也就是求这棵四叉树的深度。思路是遍历矩阵的元素，对于每一个元素，求出其相邻且比它更大的元素的深度，取其最大值加一后作为自己的深度。
采用普通的深度优先算法，需要递归调用，效率比较低。
递归过程：
如果该元素相邻元素可以访问（在边界内、比当前元素大），就依次求出邻居的深度，取最大值加一作为自己的深度。递归出口：没有可访问邻居，深度为1（只有自己）。
改进的思路
增加一个memo矩阵，作为记录。对于没有访问过的元素，置其值为0，代表没有访问过。对于访问的元素，求出当前元素的深度，存在memo中。
代码如下：
class Solution { public: int longestIncreasingPath(vector<vector<int>>& matrix) { if (matrix.size() == 0) return 0; int width = matrix[0].size(); int height = matrix.size(); int result = 0; vector<vector<int>> memo(height, vector<int>(width, 0)); for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) { int tmp = nprocess(matrix, i, j, height, width, memo); if (tmp > result) result=tmp; } return result; } int nprocess(vector<vector<int>> &matrix, int i, int j, int m, int n, vector<vector<int>> &memo) { if (memo[i][j] != 0) return memo[i][j]; memo[i][j] = 1; vector<vector<int>> shift{ { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } }; int max = 1; for (int k = 0; k < 4; k++) { int x = i + shift[k][0]; int y = j + shift[k][1]; if ((x < m) && (x >= 0) && (y<n) && (y >= 0) && (matrix[x][y]>matrix[i][j])) { int tmp = nprocess(matrix, x, y, m, n, memo) + 1; if (tmp > max) max = tmp; } } memo[i][j] = max; return max; } };
总结
重点是对于递归过程的优化。
一个问题是，将矩阵转换成四叉树。我一开始的想法，是将矩阵转换成有向图，考虑到可能存在的环路i，在深度遍历中加入了一个矩阵表示该结点是否被访问过。事实是，这个矩阵不可能是有环路的有向图（不存在a>b>…>a），这样就退化成了一棵四叉树。所以，因为没有环路的存在，是否被访问过的结点在未加入记忆矩阵的深度优先中没有作用。