329. 矩阵中的最长递增路径。这道题没有官方的题解，写下我的思路。

原题

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 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]。注意不允许在对角线方向上移动。

思路

我的思路是先将所有元素按照从小到大排序。然后开始计算，规则如下：

1. 周边的数字如果都大于当前数字，那个当前数字只能走一步，记角标1。
2. 如果周边的数字存在小于当前数字的，因为是从小到大开始计算的，那个较小的数字之前已经计算过了。因此该方向的步数为1+角标数字。当前数字的最终角标为这四个方向中的最大的。

其实也可以按照从大到小排序。

思路图

最后，还要避免空集。

最终代码

class Solution {
    func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
        guard !matrix.flatMap({$0}).isEmpty else{
            return 0
        }
        
        var longest = 1
        var allElements = Array<Item>()
        var allElementsDictionary = Dictionary<IndexPath, Int>()
        var allSteps = Dictionary<IndexPath,Int>()
        
        for (row, rowElements) in matrix.enumerated() {
            for (column, element) in rowElements.enumerated() {
                allElements.append(Solution.Item(value: element, indexPath: Solution.IndexPath(row: row, column: column)))
                allElementsDictionary[IndexPath(row: row, column: column)] = element
            }
        }
        
        allElements.sort { (currentItem, nextItem) -> Bool in
            return currentItem.value < nextItem.value
        }
        
        allElements.forEach {
            let row = $0.indexPath.row
            let column = $0.indexPath.column
            let value = $0.value
            
            var step = 1
            
            let upIndexPath = IndexPath(row: row - 1, column: column)
            if let currentStep = getStep(currentValue: allElementsDictionary[upIndexPath], currentStep: allSteps[upIndexPath], comparingWith: value) {
                
                step = max(currentStep + 1, step)
            }
            
            let leftIndexPath = IndexPath(row: row, column: column - 1)
            if let currentStep = getStep(currentValue: allElementsDictionary[leftIndexPath], currentStep: allSteps[leftIndexPath], comparingWith: value) {
                
                step = max(currentStep + 1, step)
            }
            
            let downIndexPath = IndexPath(row: row + 1, column: column)
            if let currentStep = getStep(currentValue: allElementsDictionary[downIndexPath], currentStep: allSteps[downIndexPath], comparingWith: value) {
                
                step = max(currentStep + 1, step)
            }
            
            let rightIndexPath = IndexPath(row: row, column: column + 1)
            if let currentStep = getStep(currentValue: allElementsDictionary[rightIndexPath], currentStep: allSteps[rightIndexPath], comparingWith: value) {
                
                step = max(currentStep + 1, step)
            }
            
            allSteps[IndexPath(row: row, column: column)] = step
            longest = max(step, longest)
        }
        
        return longest
    }
    
    func getStep(currentValue:Int?, currentStep:Int?, comparingWith value:Int) -> Int? {
        if let currentValue = currentValue, currentValue < value, let currentStep = currentStep {
            return currentStep
        }
        
        return nil
    }

    struct Item {
        let value:Int
        let indexPath:IndexPath
    }
    
    struct IndexPath:Hashable {
        let row:Int
        let column:Int
    }
}