矩阵中的最长递增路径

╰半橙微兮° 2023-02-14 15:53 131阅读 0赞

## 一、前言 ##

问题来源LeetCode 329，难度：困难

问题链接：[https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix][https_leetcode-cn.com_problems_longest-increasing-path-in-a-matrix]

## 二、题目 ##

给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = 
    [
      [9,9,4],
      [6,6,8],
      [2,1,1]
    ] 
    输出: 4 
    解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入: nums = 
    [
      [3,4,5],
      [3,2,6],
      [2,2,1]
    ] 
    输出: 4 
    解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

## 三、思路 ##

三种解法

### 3.1 方法一：朴素的深度优先搜索 ###

时间复杂度：O(2^(m+n)),空间复杂度：O(mn)

### 3.2 方法二：带备忘录的深度优先搜索 ###

时间复杂度：O(mn),空间复杂度：O(mn)

### 3.3 方法三：拓扑排序+记忆化搜索 ###

时间复杂度：O(mn),空间复杂度：O(mn)

**拓扑排序步骤：**

*  从DGA图中找到一个没有前驱的顶点输出。(可以遍历，也可以用优先队列维护)
 *  删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点)
 *  重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！

输出并删除没有前驱的顶点，一直重复这个过程。对应本题中整数矩阵，没有前驱的顶点就是最小的数，找到最小的数就可以确定它上下左右位置上的数最长路径。

拓扑排序原理可以参考：[https://www.cnblogs.com/bigsai/p/11489260.html][https_www.cnblogs.com_bigsai_p_11489260.html]

## 四、编码技巧 ##

在判断上下左右坐标的时候，可以定义一个数组保存上下左右移动的坐标增量，这样就可以通过循环来进行坐标点判断。而不用进行四次坐标点判断了。

static const int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };  // 分别是 向后、向下、向左、向上
    for (int i = 0; i < 4; ++i)
    {
        int nh = ph + dirs[i][0];
        int nx = px + dirs[i][1];
        if (nh >= 0 && nh <= maxH && nx >= 0 && nx <= maxX && matrix[ph][px] < matrix[nh][nx])
        {
            int ret = longestIncreasingPath(matrix, nh, nx) + 1;
            maxPath = max(maxPath, ret);
        }
    }

## 五、编码实现 ##

//==========================================================================
    /**
    * @file : 329_LongestIncreasingPath.h
    * @title: 矩阵中的最长递增路径
    * @purpose : 给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
    *
    * 示例 1:
    * 输入: nums =
    * [
    *   [9,9,4],
    *   [6,6,8],
    *   [2,1,1]
    * ]
    * 输出: 4
    * 解释: 最长递增路径为 [1, 2, 6, 9]。
    *
    *
    * 示例 2:
    * 输入: nums =
    * [
    *   [3,4,5],
    *   [3,2,6],
    *   [2,2,1]
    * ]
    * 输出: 4
    * 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
    *
    * 来源：力扣（LeetCode）难道：困难
    * 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
    */
    //==========================================================================
    
    #pragma once
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    // 以下为测试代码
    #define NAMESPACE_LONGESTINCREASINGPATH namespace NAME_LONGESTINCREASINGPATH {
    #define NAMESPACE_LONGESTINCREASINGPATHEND }
    
    NAMESPACE_LONGESTINCREASINGPATH
    
    // 方法一：朴素的深度优先搜索 【超时】
    // 时间复杂度：O(2^(m+n)),空间复杂度：O(mn)
    class Solution_1 
    {
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) 
        {
            if (matrix.empty() || matrix[0].empty())
                return 0;
    
            int maxH = (int)matrix.size();
            int maxX = (int)matrix[0].size();
            
            for (int i = 0; i < maxH; ++i)
            {
                if (maxX != matrix[0].size())
                {
                    cout << "输入参数错误" << endl;
                    return 0;
                } 
            }
    
            int maxPath = 0;
            for (int h = 0; h < maxH; ++h)
            {
                for (int x = 0; x < maxX; ++x)
                {
                    maxPath = max(maxPath, longestIncreasingPath(matrix, h, x));
                }
            }
    
            return maxPath;
        }
    
    private:
        // 二维数组 matrix[h][x]
        int longestIncreasingPath_old(vector<vector<int>>& matrix, int ph, int px)
        {
            // matrix 是一个二维数组，这里不再校验
            if (matrix.empty() || ph < 0 || ph > matrix.size() || px < 0 || px > matrix[0].size())
                return 0;
            
            int maxH = (int)matrix.size() - 1;
            int maxX = (int)matrix[0].size() - 1;
            int maxPath = 1;
            // 向右
            if (px < maxX)
            {
                if (matrix[ph][px] < matrix[ph][px + 1])
                {
                    int ret = longestIncreasingPath(matrix, ph, px+1) + 1;
                    maxPath = max(maxPath, ret);
                }
            }
    
            // 向下
            if (ph > 0)
            {
                if (matrix[ph][px] < matrix[ph - 1][px])
                {
                    int ret = longestIncreasingPath(matrix, ph-1, px) + 1;
                    maxPath = max(maxPath, ret);
                }
            }
    
            // 向左
            if (px > 0)
            {
                if (matrix[ph][px] < matrix[ph][px - 1])
                {
                    int ret = longestIncreasingPath(matrix, ph, px - 1) + 1;
                    maxPath = max(maxPath, ret);
                }
            }
    
            // 向上 
            if (ph < maxH)
            {
                if (matrix[ph][px] < matrix[ph + 1][px])
                {
                    int ret = longestIncreasingPath(matrix, ph + 1, px) + 1;
                    maxPath = max(maxPath, ret);
                }
            }
            return maxPath;
        }
    
        // 二维数组 matrix[h][x]
        int longestIncreasingPath(vector<vector<int>>& matrix, unsigned int ph, unsigned int px)
        {
            // matrix 是一个二维数组，这里不再校验
            if (matrix.empty() || ph > matrix.size() || px > matrix[0].size())
                return 0;
    
            int maxH = (int)matrix.size() - 1;
            int maxX = (int)matrix[0].size() - 1;
            static const int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };  // 分别是 向后、向下、向左、向上
    
            int maxPath = 1;
            for (int i = 0; i < 4; ++i)
            {
                int nh = ph + dirs[i][0];
                int nx = px + dirs[i][1];
                if (nh >= 0 && nh <= maxH && nx >= 0 && nx <= maxX && matrix[ph][px] < matrix[nh][nx])
                {
                    int ret = longestIncreasingPath(matrix, nh, nx) + 1;
                    maxPath = max(maxPath, ret);
                }
            }
      
            return maxPath;
        }
    };
    
    // 方法二：记忆化深度优先搜索
    // 时间复杂度：O(mn),空间复杂度：O(mn)
    class Solution_2
    {
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix)
        {
            if (matrix.empty() || matrix[0].empty())
                return 0;
    
            int maxH = (int)matrix.size();
            int maxX = (int)matrix[0].size();
            for (int i = 0; i < maxH; ++i)
            {
                if (maxX != matrix[0].size())
                {
                    cout << "输入参数错误" << endl;
                    return 0;
                }
            }
    
            vector<vector<int>> cache(matrix.size(), vector<int>(maxX, 0));
            int maxPath = 0;
            for (int h = 0; h < maxH; ++h)
            {
                for (int x = 0; x < maxX; ++x)
                {
                    maxPath = max(maxPath, longestIncreasingPath(matrix, h, x, cache));
                }
            }
    
            return maxPath;
        }
    
    private:
        // 二维数组 matrix[h][x]
        int longestIncreasingPath(vector<vector<int>>& matrix, int ph, int px, vector<vector<int>>& cache)
        {
            // matrix 是一个二维数组，这里不再校验
            if (matrix.empty() || ph > matrix.size() || px > matrix[0].size())
                return 0;
    
            if (cache[ph][px] != 0)
                return cache[ph][px];
            
            int maxH = (int)matrix.size() - 1;
            int maxX = (int)matrix[0].size() - 1;
            static const int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };  // 分别是 向后、向下、向左、向上
    
            int maxPath = 0;
            for (int i = 0; i < 4; ++i)
            {
                int nh = ph + dirs[i][0];
                int nx = px + dirs[i][1];
                if (nh >= 0 && nh <= maxH && nx >= 0 && nx <= maxX && matrix[ph][px] < matrix[nh][nx])
                {
                    cache[nh][nx] = longestIncreasingPath(matrix, nh, nx, cache);
                    maxPath = max(maxPath, cache[nh][nx]);
                }
            }
    
            return ++maxPath;
        }
    };
    
    // 方法三：拓扑排序+记忆化搜索
    // 时间复杂度：O(mn),空间复杂度：O(mn)
    class Solution_3 
    {
        struct Point
        {
            int h, x, v;
            Point(int ih, int ix, int iv) :h(ih), x(ix), v(iv) {}
        };
    
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) 
        {
            if (matrix.size() == 0)
                return 0;
            const int maxH = (int)matrix.size();
            const int maxX = (int)matrix[0].size();
            vector<vector<int>> dp(maxH, vector<int>(maxX, 1));
            vector<Point> vp;
            vp.reserve(maxH * maxX);
            for (int i = 0; i < maxH; i++)
            {
                for (int j = 0; j < maxX; j++)
                {
                    vp.push_back(Point(i, j, matrix[i][j]));
                }
            }
    
            // 对坐标排序
            sort(vp.begin(), vp.end(), [](const Point& lhs, const Point& rhs) { return lhs.v < rhs.v; });
    
            int ret = 1;
            static const int dirs[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };  // 分别是 向后、向下、向左、向上
            for (const auto& p : vp) 
            {
                auto h = p.h;
                auto x = p.x;
                auto v = p.v;
                for (int i = 0; i < 4; ++i)
                {
                    int nh = h + dirs[i][0];
                    int nx = x + dirs[i][1];
                    if (nh >= 0 && nh < maxH && nx >= 0 && nx < maxX && matrix[h][x] < matrix[nh][nx])
                    {
                        dp[nh][nx] = dp[h][x] + 1;
                        ret = max(ret, dp[nh][nx]);
                    }
                }
            }
            return ret;
        }
    };
    //
    // 测试 用例 START
    
    void test(const char* testName, vector<vector<int>>& data, int expect)
    {
        Solution_1 S1;
        Solution_2 S2;
        Solution_3 S3;
    
        int result1 = S1.longestIncreasingPath(data);
        int result2 = S2.longestIncreasingPath(data);
        int result3 = S3.longestIncreasingPath(data);
    
        if (result1 == expect && result2 == expect && result3 == expect)
        {
            cout << testName << ", solution123 passed." << endl;
        }
        else
        {
            cout << testName << ", solution failed. result1:" << result1 << " ,result2: " << result2 << " ,result3: " << result3 << endl;
        }
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<int>> data =
        {
            { 9 }
        };
        int expect = 1;
    
        test("Test1()", data, expect);
    }
    
    // 测试用例
    void Test2()
    {
        vector<vector<int>> data =
        {
            { 9, 1 }
        };
        int expect = 2;
    
        test("Test2()", data, expect);
    }
    
    // 测试用例
    void Test3()
    {
        vector<vector<int>> data =
        {
            { 1, 9 }
        };
        int expect = 2;
    
        test("Test3()", data, expect);
    }
    
    // 测试用例
    void Test4()
    {
        vector<vector<int>> data = 
        {
            { 9, 9, 4 },
            { 6, 6, 8 },
            { 2, 1, 1 } 
        };
        int expect = 4;
    
        test("Test4()", data, expect);
    }
    
    void Test5()
    {
        vector<vector<int>> data =
        {
            { 3, 4, 5 },
            { 3, 2, 6 },
            { 2, 2, 1 }
        };
        int expect = 4;
    
        test("Test5()", data, expect);
    }
    
    void Test6()
    {
        vector<vector<int>> data =
        {
            { 5, 6, 7 },
            { 4, 1, 8 },
            { 3, 2, 9 }
        };
        int expect = 9;
    
        test("Test6()", data, expect);
    }
    
    NAMESPACE_LONGESTINCREASINGPATHEND
    // 测试 用例 END
    //
    
    void LongestIncreasingPath_Test()
    {
        NAME_LONGESTINCREASINGPATH::Test1();
        NAME_LONGESTINCREASINGPATH::Test2();
        NAME_LONGESTINCREASINGPATH::Test3();
        NAME_LONGESTINCREASINGPATH::Test4();
        NAME_LONGESTINCREASINGPATH::Test5();
        NAME_LONGESTINCREASINGPATH::Test6();
    }

**执行结果：**

![20200603195346787.png][]

[https_leetcode-cn.com_problems_longest-increasing-path-in-a-matrix]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
[https_www.cnblogs.com_bigsai_p_11489260.html]: https://www.cnblogs.com/bigsai/p/11489260.html
[20200603195346787.png]: https://img-blog.csdnimg.cn/20200603195346787.png