[LeetCode]Longest Increasing Path in a Matrix

Matrix的问题有的时候可以转化成图的问题来求解。对于这道题也是一样，我们可以转化成有向图，每一个cell就是一个vertex。而每一个vertex有四个可能的邻节点，如果相邻节点a的值大于当前节点值，那么可以视作从当前节点有一条有向边去向节点a。根据这个原则，我们可以把图给建起来。值得注意的是，这个图没有环，因为假设存在环的话，对于环上的每个节点我们有n1 < n2 < n3 <...< nk < n1，这是不可能出现的。那么这道题就可以转外成求DAG里面的最长路径问题，dfs当然可以做，但是显然会超时。Topological sorting可以解决这个问题，DAG里的最长路径就是topological sorting之后的最长路径，把每一层没有indegree或者outdegree的节点去掉，最后的层数就是我们要的最长路径。代码如下：

	class Solution {
	public:
	int longestIncreasingPath(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	vector<vector<int>> padding(m + 2, vector<int>(n + 2, INT_MIN));
	vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	for(int i = 0; i < m; ++i)
	for(int j = 0; j < n; ++j)
	padding[i + 1][j + 1] = matrix[i][j];
	vector<vector<int>> outdegrees(m + 2, vector<int>(n + 2, 0));
	for(int i = 1; i <= m; ++i)
	{
	for(int j = 1; j <= n; ++j)
	{
	for(auto& dir: dirs)
	{
	if(padding[i][j] < padding[i + dir.first][j + dir.second])
	++outdegrees[i][j];
	}
	}
	}
	//get leaves
	queue<int> leaves;
	for(int i = 1; i <= m; ++i)
	for(int j = 1; j <= n; ++j)
	if(!outdegrees[i][j])
	leaves.push(i * (n + 2) + j);
	//peeling onion
	int len = 0;
	while(leaves.size())
	{
	++len;
	int size = leaves.size();
	while(size-- > 0)
	{
	int leave = leaves.front();
	leaves.pop();
	int i = leave / (n + 2), j = leave % (n + 2);
	for(auto& dir: dirs)
	{
	if(padding[i][j] > padding[i + dir.first][j + dir.second])
	if(--outdegrees[i + dir.first][j + dir.second] == 0)
	leaves.push((i + dir.first) * (n + 2) + j + dir.second);
	}
	}
	}
	return len;
	}
	};

view raw Sequence Reconstruction.cpp hosted with ❤ by GitHub

时间复杂度O(V + E) = O(m * n)，空间复杂度O(m * n)。
如果在dfs的时候做memorization的优化，也可以达到我们想要的结果。时间复杂度也是O(V + E) = O(m * n)，因为对于每一个节点和每一条边都只会计算一次了。空间复杂度O(m * n)。代码如下：

	class Solution {
	public:
	vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	int longestIncreasingPath(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, res = 0;
	unordered_map<int, int> map;
	for(int i = 0; i < m; ++i)
	for(int j = 0; j < n; ++j)
	res = max(res, dfs(matrix, map, i, j));
	return res;
	}
	private:
	int dfs(vector<vector<int>>& matrix, unordered_map<int, int>& map, int x, int y)
	{
	int m = matrix.size(), n = matrix[0].size(), len = 1;
	if(map.count(x * n + y))return map[x * n + y];
	for(auto& dir : dirs)
	{
	int i = x + dir.first, j = y + dir.second;
	if(i >= 0 && i < m && j >= 0 && j < n && matrix[i][j] > matrix[x][y])
	len = max(len, dfs(matrix, map, i, j) + 1);
	}
	map[x * n + y] = len;
	return len;
	}
	};

view raw Longest Increasing Path in a Matrix2.cpp hosted with ❤ by GitHub