LeetCode 329. Longest Increasing Path in a Matrix-白红宇

LeetCode 329. Longest Increasing Path in a Matrix

阅读量：6155 次

发布时间：2019-06-21

本文共 1798 字，大约阅读时间需要 5 分钟。

如果把矩阵元素看做点，小的元素到打的元素看做边连起来，这道题等价于在一个有向图中寻找最长路径。

第一想法是用dfs或bfs，但是直接做超时了。以dfs为例，时间复杂度为O(2^(m+n))，空间复杂度O(h)=O(mn)

由于dfs中很多节点的最长路径都被重复计算了，因此可以 Memorization 将结果保存下来。

方法一：DFS+Memoization

每条边和每个节点都只访问了一次，O(V+E)，O(V)=O(mn)，O(E)=O(4V)=O(mn)，所以时间复杂度O(mn)

空间复杂度O(mn)

class Solution {public:    vector
     
      
       > dirs={
   {
   0,1},{
   0,-1},{
   1,0},{-1,0}};        int longestIncreasingPath(vector
       
        
         >& matrix) {        int m=matrix.size(), n=m==0?0:matrix[0].size();        vector
         
          
           > cache(m,vector
           
            (n,0)); int res=0; for (int i=0;i

> &matrix, int i, int j, vector

> &cache){ if (cache[i][j]!=0) return cache[i][j]; int max_len=1; for (auto dir:dirs){ int x=i+dir[0], y=j+dir[1]; if (x>=0 && x

=0 && y

matrix[i][j]){ max_len = max(max_len, 1+dfs(matrix,x,y,cache)); } } cache[i][j] = max_len; return max_len; }};

方法二：Topological Sort

由于这道题四个方向都可以，如果用dp来做是很麻烦的，dp[i]依赖的四个方向的dp值不一定是已经求得的。所以要用DP来做的话，需要用拓扑的顺序来依次更新dp。

由于这道题比较简单，也不需要dp了，直接用拓扑排序来做。用入度做和出度做本题没区别。

class Solution {public:    vector
     
      
       > dirs={
   {
   0,1},{
   0,-1},{
   1,0},{-1,0}};        int longestIncreasingPath(vector
       
        
         >& matrix) {        int m=matrix.size(), n=m==0?0:matrix[0].size();        vector
         
          
           > indegree(m,vector
           
            (n,0)); // calculate indegree for (int i=0;i
            
             =0 && x
             
              =0 && y
              
               > q; for (int i=0;i
               
                =0 && x
                
                 =0 && y
                 
                  matrix[i][j]){ --indegree[x][y]; if (indegree[x][y]==0){ q.push({x,y}); //cout << x << ' ' << y << endl; } } } } } } return len; }};