Leetcode 每日一题：Longest Increasing Path in a Matrix

写在前面：

今天我们继续看一道图论和遍历相关的题目。这道题目的背景是在一个矩阵当中找寻最长的递增数列长度。思路上非常好想，绝对和 DFS 相关，但是题目的优化要求非常高，对于语言和内存特性的考察特别丰富，如果是单纯的 Leetcoder 或者是扎根算法而语言相对专精较弱的同学，这道题目可能很难做到 AC，就让我们一起来看看吧！

题目介绍：

题目信息：

题目链接：https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
题目类型：Array，Graph，DFS，Dynamic Programming(是的，可以拿 dp 做，但是太难了而且并不具备推广价值，所以不分享了)
题目难度：Hard（思路 easy，优化要求 hard）
题目来源：Google 高频面试真题

题目问题：

给定一个大小为 m * n 的矩阵，每一个矩阵的位置都代表一个 value
找出最长的递增遍历行走路线
在行走的过程中，只能上下左右，不能走对角线
例子：

题目想法：

深度优先暴力解法：

一看到是走 “最长的递增” 数组，并且在图中只能上下左右移动，我们很容易可以想到 DFS，这也是一个标准的 DFS 问题。我们只需要遍历每一个位置当作起点，并且不断寻找周围有没有递增的位置可以让我们前进，返回当前起点所能达到的最大值。将所有的最大值统筹起来，进行返回。

很可惜，思路很美好，现实很骨感，这样的做法不仅会 TLE，而且会 MLE，在算法时间复杂度和占用空间内存的角度来讲都会爆炸。

Runtime：O(2^(m+n)) --> 我们需要遍历所有可能的子数组

Space：O(mn) --> 我们最坏需要遍历所有的 node 和 edge，并且，需要mn次 stack 来储存

太慢，也太耗空间了（如果懂得堆栈的小伙伴应该知道太多 recursion 会占掉很多内存）

时间复杂度优化：

暴力解法非常简单想到，那 Google 和其他大厂的要求肯定不止这么一点儿～～但如果自己想想，我们每一次以一个点为起点进行探索的时候，我们的目标都是取得这个点所能创造的最大长度，从而决定我们是否有机会获得更好的结果。那我们是否可以利用 Memoization 的方法，将每个遍历过后的点的最大值记下来，这样之后的重复使用不就都不用再遍历了吗？

我们在从每一个点开始遍历 DFS 的时候，将所有路过的点的最大值进行一个更新，而我们在找寻起点的过程中，就可以直接从这些点里取值了，因为他一定是最大的。

为什么一定如果一个点被遍历过之后存下的结果一定 >= 我们以这个点为起点重新遍历呢？

如果这个点的现有最大值是从本点开始，那再来一次遍历也会得到相同结果
如果这个点的现有最大值是从一个比他更小的点得来的，那以他自己为起点此次结果一定会小于我们所存储的节点，因为单调递增的单向性
而这个点的现有最大值不可能来自己于一个比他更大的起点
所以总结，存下的结果 >= 以当前为起点遍历可能最大 ---> 当前存储的结果一定是最优的

Runtime：O(mn) ---> 我们只需要遍历一次图即可，可以被 AC

Space：O(mn) ---> 我们需要存储所有的矩阵点的最大值

内存优化：

虽然这道题的 O(mn) 的空间复杂度已经是最优复杂度了，但不同的 implementation 同样会导致 AC 和 MLE 的区别，题主自己在做这道题的时候，经过了算法的优化以后还是 MLE，后来经过对数据结构和 recursion 变量的优化才最终解决内存问题，这可能也是大厂对代码水平更高难度的考察吧，这也是我认为这道题是 hard 的一部分原因

如果使用 C++ 进行代码编写，可以优化的点有：

对于数据的存储，不使用 vector，而是使用 dynamic array 进行内存分配
对于Recursion函数传入的矩阵和记忆矩阵，把他们变成 member variable，在recursion中静态调用，而不是不停的动态参数传入

第一个问题的原因是基于 vector 的特性。在 C++中，动态数组的内存分布并不是按照有多少个元素来分配的，而是分配 2^n 个储存空间，n 是让 2^n 大于所需长度的最小值。而这样的分配方式会造成内存浪费。例如：一个长度为 7 的 vector 实际上占用了 8 个长度的内存，而长度为 9 的 vector 实际上占用了 16 个长度的内存。而如果使用 dynamic allocation，在 matrix 长度宽度已知不会变的情况下，我们完全可以手动分配内存，精准的将矩阵的维度分配出来。在 2 个维度同时减少内存浪费，省去非常多的空间

第二个问题的原因是，没有一次 recursion function call，这个函数就会在内存中开辟一段储存空间，而如果我们将矩阵和记忆矩阵作为变量不断传入，他们就会不断的在内存 stack 中生成很多很多 copy，从而导致 stack 崩掉。而如果我们将其改成 member variable，他们相对于所有的 recursion 函数就是全局的，每个 recursion 都只需要直接调用他的指针所指的真实数据，而不是 copy，这也会节省更多空间

在同时完成这两个优化以后，相信大家也能成功 AC 这道 Leetcode hard

题目代码：

class Solution {
public:int x[4] = {0, 1, 0, -1};int y[4] = {1, 0, -1, 0};int** maxViewed;      //use dynamic array instead of vector to prevent memory wasteint** matrix;         //use member variable instead of arguement in recursion to prevent //too much stack memory wasted in recursionint DFS(int i, int j, int m, int n){//we have already seen this point, so need to traverse. if(maxViewed[i][j] != 0){return maxViewed[i][j];}for(int d = 0; d < 4; d++){int new_i = i + x[d];int new_j = j + y[d];//check in bound, no need to check revisit, but have check for increasingif(new_i < m && new_i >= 0 && new_j < n && new_j >= 0){if(matrix[i][j] < matrix[new_i][new_j]){maxViewed[i][j] = max(DFS(new_i, new_j, m, n), maxViewed[i][j]);}}}maxViewed[i][j] += 1;return maxViewed[i][j];}int longestIncreasingPath(vector<vector<int>>& matrix_target) {int maxDist = 0;int m = matrix_target.size(), n = matrix_target[0].size();//create a cache and matrix storage for the traversing:maxViewed = new int*[m];  // Allocate memory for rowsmatrix = new int*[m];for (int i = 0; i < m; ++i) {maxViewed[i] = new int[n];  // Allocate memory for columnsmatrix[i] = new int[n];}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){maxViewed[i][j] = 0;matrix[i][j] = matrix_target[i][j];}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){maxDist = max(maxDist, DFS(i, j, m, n));}}return maxDist;}
};