49ms c++ LCS


  • 0
    T
    /*	f[i]以i为尾的最长个数。
    	结构体Node存坐标和值;
    	将左右的点放入一个vector里面,然后按照值从小到大排序。
    	从头到尾遍历vector,当前点nums[i]的上下左右, f[i]=max(f[上,下,左,右]) if nums[上,下,左,右] < nums[i]
    	fm[][]存对应位置的f[i]值,方便读取
    */
    class Solution {
    public:
        struct Node
        {
            int x,y,val;
        };
        int longestIncreasingPath(vector<vector<int> >& matrix) {
            int ans=-1, m=matrix.size();
            if (m==0) return 0;
            int n=matrix[0].size(),len = m*n;
            int f[len+5]={0};
            vector<vector<int> > fm(m,vector<int>(n));
            vector<Node>nums;
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    struct Node tmp={i,j,matrix[i][j]};
                    nums.push_back(tmp);
                }
            sort(nums.begin(),nums.end(),cmp);
            int dx[4]={1,-1,0,0};
            int dy[4]={0,0,1,-1};
            for(int i=0;i<len;i++)
            {
                for(int j=0;j<4;j++)
                {
                    int tmpx = nums[i].x+dx[j], tmpy = nums[i].y+dy[j];
                    if (tmpx>=0 && tmpx<m && tmpy>=0 && tmpy<n && matrix[tmpx][tmpy]<nums[i].val) f[i]=max(f[i],fm[tmpx][tmpy]);
                }
                ans=max(ans,++f[i]);
                fm[nums[i].x][nums[i].y]=f[i];
            }
            return ans;
        }
        static bool cmp(Node a,Node b)
        {
            return a.val<b.val;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.