矩阵时间复杂度分析中的最长递增路径
Longest Increasing Path in a Matrix Time Complexity Analysis
我正在研究以下算法：
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
我最初的冲动是在每个方向上有 4 个功能，这些功能具有递增的价值。例如，如果整数 1 在 [1,1] 中，并且该单元格周围的四个值递增，则将创建三个函数。这个过程，在最坏的情况下，对于每个单元格，我相信是 O(4^(M*N) [每个元素调用 4 个函数，并且有 mxn 个元素]。
但是，解决方案建议使用以下蛮力（在他们继续使用记忆优化它之前）：
Algorithm
Each cell can be seen as a vertex in a graph G. If two adjacent cells have value a < ba<b, i.e. increasing then we have a directed edge (a, b)(a,b). The problem then becomes:
Search the longest path in the directed graph G.
Naively, we can use DFS or BFS to visit all the cells connected starting from a root. We update the maximum length of the path during search and find the answer when it finished.
Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section.
Java
// Naive DFS Solution
// Time Limit Exceeded
public class Solution {
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
m = matrix.length;
n = matrix[0].length;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j));
return ans;
}
private int dfs(int[][] matrix, int i, int j) {
int ans = 0;
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
ans = Math.max(ans, dfs(matrix, x, y));
}
return ++ans;
}
}
这个算法的时间复杂度非常相似（在最坏的情况下对单个单元仅启动 4 个 dfs 函数）具有以下复杂度分析：
Complexity Analysis
Time complexity : O(2^{m+n))
). The search is repeated for each valid increasing path. In the worst case we can have O(2^{m+n)) calls. For example:
1 2 3 . . . n
2 3 . . . n+1
3 . . . n+2
. .
. .
. .
m m+1 . . . n+m-1
Space complexity : O(mn). For each DFS we need O(h) space used by the system stack, where hh is the maximum depth of the recursion. In the worst case, O(h) =O(mn).
我不明白他们是如何得到这个时间复杂度或 space 复杂度的。对于 space 成本，我想最坏的情况是矩阵按行和列升序排序，但单个堆栈将大致与 mxn 正方形的对角线长度成正比。这就是为什么 space 是最坏情况与 O(mn) 成正比的原因吗？另外，space 的成本是 O(2^(m+n)) 而不是 O(4^(m*n)？
我相信 Sunny 是正确的，暴力搜索的时间复杂度为 O(4^(m*n))，其中 n 和 m 是矩阵中的行数和列数与给定数组关联。我想建议一个 O(n*m) 算法和实现它的 Ruby 代码。
在诸如此类的问题中，倾向于考虑从矩阵中的每个元素移动到所有相邻的较大值元素（最多 4 个），然后从这些元素中的每一个移动到它们所有相邻的较大值元素- 值元素，依此类推（因此为 O(4^m*n)）。但是，由于路径必须增加，我们可以用不同的方式来看待问题，从而开发出高效的优化算法。
假设我们按值对所有位置进行分组。对于问题中给出的示例，可以表示为：
value_to_locs
#=> { 9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]], 8=>[[1, 2]],
# 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
接下来让我们按降序考虑散列值：
to_process = value_to_locs.keys.sort.reverse
#=> [9, 8, 6, 4, 2, 1]
首先我们处理值为9的两个位置。从这两个位置开始的递增路径的长度显然是 1（路径是 [[0, 0]] 和 [[1, 0]]），因为无处可去。我们将此信息保存到一个先前为空的散列 processed，现在是：
processed = { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil } }
接下来考虑值为 8（to_process 的第二个元素）[1, 2] 的单个位置。如果从该位置开始的递增路径的长度大于 1，则它接下来必须转到 processed 的元素之一。 [1, 2] 既不与 [0, 0] 相邻，也不与 [1, 1] 相邻，因此我们添加键值对：
[1, 2]=>{ len: 1, next: nil }
到processed，获得
processed
#=> { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil },
# [1, 2]=>{ len: 1, next: nil } }
要检查的下一个值（在 to_process 中）是 6，它出现在两个位置，[1, 0] 和 [1, 1]。前者与 processed ([0, 0]) 中的一个位置相邻，因此我们将键值对
添加到 processed
[1, 0]=>{ len: 1 + processed[[0, 0]][:len], next: [0, 0] }
#=>{ len: 2, next: [0, 0] }
另一个值为6、[1, 1]的元素在processed、[0, 1]和[1, 2]中有两个相邻的元素，所以添加
[1, 1]=>{ len: 1 + processed[[0, 1]][:len], next: [0, 1] }
#=>{ len: 2, next: [0, 1] }
或
[1, 1]=>{ len: 1 + processed[[1, 2]][:len], next: [1, 2] }
#=>{ len: 2, next: [1, 2] }
到processed，即:len的值最大的那个。 （这里是平局，所以可以选择其中一个。）
以此类推，直到原数组的所有元素都是processed中的键。然后我们将processed[loc][:len]最大的位置loc作为最长递增路径的起点select，并重构相关路径。
请注意，密钥 :next 仅用于重建最长路径。如果只需要最长路径的长度，则不需要该密钥。
代码
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
value_to_locs.keys.sort.reverse.each do |x|
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
low, high = value_to_locs.keys.minmax
high.downto(low) do |x|
next unless value_to_locs.key?(x)
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def greater_neighbors((r,c), arr, row_indices, col_indices)
curr_val = arr[r][c]
[[-1,0], [1,0], [0,-1], [0, 1]].each_with_object([]) do |(rdelta, cdelta), a|
ra = r + rdelta
ca = c + cdelta
a << [ra, ca] if row_indices.cover?(ra) && col_indices.cover?(ca) &&
curr_val < arr[ra][ca]
end
end
def extract_path(processed)
loc, g = processed.max_by { |loc,g| g[:len] }
len = g[:len]
path = [loc]
loop do
break if g[:next].nil?
loc = g[:next]
path << loc
g = processed[loc]
end
[len, path]
end
例子
#1
arr = [
[9,9,4],
[6,6,8],
[2,1,1]
]
longest_increasing_path(arr)
#=> [4, [[2, 1], [2, 0], [1, 0], [0, 0]]]
#2
rows = 10
cols = 10
a = (1..9).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
#=> [[4, 7, 5, 3, 5, 4, 2, 2, 9, 3],
# [8, 3, 3, 5, 4, 2, 8, 1, 8, 3],
# [7, 1, 9, 4, 2, 7, 1, 4, 4, 6],
# [3, 7, 5, 5, 2, 3, 9, 1, 9, 7],
# [2, 6, 7, 1, 5, 9, 3, 5, 2, 9],
# [4, 4, 6, 7, 8, 4, 9, 7, 6, 1],
# [9, 7, 5, 4, 6, 8, 8, 4, 4, 8],
# [3, 1, 9, 9, 5, 7, 9, 6, 7, 2],
# [5, 6, 4, 8, 2, 3, 4, 3, 3, 9],
# [7, 9, 6, 9, 5, 2, 9, 7, 6, 3]]
require 'time'
t = Time.now
longest_increasing_path(arr)
#=> [5, [[6, 3], [6, 2], [5, 2], [5, 3], [5, 4]]]
Time.now - t
#=> 0.003606 seconds
因此，最长路径的长度为 5，包含元素 4，在 [6, 3]，然后左至 5，直至 6， 7 的权利，8 的权利。
#3
rows = 100
cols = 200
a = (1..20).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
t = Time.now
len, path = longest_increasing_path(arr)
#=> [12, [[86, 121], [86, 120], [86, 119], [87, 119], [87, 118], [86, 118],
# [85, 118], [85, 117], [86, 117], [87, 117], [88, 117], [89, 117]]]
Time.now - t
#=> 0.153562 seconds
path.map { |r,c| arr[r][c] }
#=> [1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 19, 20]
说明
首先让我们考虑示例#1 的辅助方法greater_neighbors。如图所示为arr，
row_indices = 0..arr.size-1
#=> 0..2
col_indices = 0..arr.first.size-1
#=> 0..2
接下来，（将 arr 视为矩阵）我们将具有相同值的位置分组：
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
#=> {9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]],
# 8=>[[1, 2]], 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
processed = {}
此散列将包含已检查的位置。
low, high = value_to_locs.keys.minmax
#=> [1, 9]
这提供了处理具有给定值的位置的顺序，从 high 到 low。
enum0 = high.downto(low)
#=> #<Enumerator: 9:downto(1)>
生成enum0的第一个元素并传递给块：
x = enum0.next
#=> 9
和
value_to_locs.key?(x)
#=> true
被执行了，所以我们不执行next.
我们现在考虑所有值为 9 的位置，然后是值为 8 的位置，依此类推。
生成9后传给block，next没有执行，进行如下计算：
b = value_to_locs[x]
#=> [[0, 0], [0, 1]]
enum1 = b.each
#=> #<Enumerator: [[0, 0], [0, 1]]:each>
loc = enum1.next
#=> [0, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
方法greater_neighbors简单地构造了一个数组，其中包含与loc相邻的所有位置，其值大于loc处的值。
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> nil
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>1, :next=>nil}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}}
我们现在生成 enum1 的下一个和最后一个元素并将其传递给块：
loc = enum1.next
#=> [0, 1]
此位置的计算与 [0, 0] 的计算类似，结果为：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil}}
我们到达了enum1的最后一个元素，所以我们接下来执行：
x = enum0.next
#=> 8
value_to_locs.key?(x)
#=> true # so next is not executed
b = value_to_locs[x]
#=> [[1, 2]]
enum1 = b.each
#=> #<Enumerator: [[1, 2]]:each>
loc = enum1.next
#=> [1, 2]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
同样，从这个位置无处可去，所以我们得到：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}}
继续，
x = enum0.next
#=> 7
value_to_locs.key?(x)
#=> false # so next is executed
x = enum0.next
#=> 6
value_to_locs.key?(x)
#=> true # so next is executed
b = value_to_locs[x]
#=> [[1, 0], [1, 1]]
enum1 = b.each
#=> #<Enumerator: [[1, 0], [1, 1]]:each>
loc = enum1.next
#=> [1, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> [[0, 0]]
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> [0, 0]
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>2, :next=>[0, 0]}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]}}
最后，我们来到了一个与更高价值的位置 ([0, 0]) 相邻的位置 ([1, 0])。
以这种方式继续计算，直到我们得到：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]},
# [1, 1]=>{:len=>2, :next=>[0, 1]}, [0, 2]=>{:len=>2, :next=>[1, 2]},
# [2, 0]=>{:len=>3, :next=>[1, 0]}, [2, 1]=>{:len=>4, :next=>[2, 0]},
# [2, 2]=>{:len=>2, :next=>[1, 2]}}
剩下的就是找到k=>v最大的键值对k=>v，然后提取最长的路径。这是由助手 extract 完成的，它与 greater_neighbors 一样简单。
我正在研究以下算法：
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
我最初的冲动是在每个方向上有 4 个功能，这些功能具有递增的价值。例如，如果整数 1 在 [1,1] 中，并且该单元格周围的四个值递增，则将创建三个函数。这个过程，在最坏的情况下，对于每个单元格，我相信是 O(4^(M*N) [每个元素调用 4 个函数，并且有 mxn 个元素]。
但是，解决方案建议使用以下蛮力（在他们继续使用记忆优化它之前）：
Algorithm
Each cell can be seen as a vertex in a graph G. If two adjacent cells have value a < ba<b, i.e. increasing then we have a directed edge (a, b)(a,b). The problem then becomes:
Search the longest path in the directed graph G.
Naively, we can use DFS or BFS to visit all the cells connected starting from a root. We update the maximum length of the path during search and find the answer when it finished.
Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section.
Java
// Naive DFS Solution
// Time Limit Exceeded
public class Solution {
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
m = matrix.length;
n = matrix[0].length;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j));
return ans;
}
private int dfs(int[][] matrix, int i, int j) {
int ans = 0;
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
ans = Math.max(ans, dfs(matrix, x, y));
}
return ++ans;
}
}
这个算法的时间复杂度非常相似（在最坏的情况下对单个单元仅启动 4 个 dfs 函数）具有以下复杂度分析：
Complexity Analysis
Time complexity : O(2^{m+n))
). The search is repeated for each valid increasing path. In the worst case we can have O(2^{m+n)) calls. For example:
1 2 3 . . . n
2 3 . . . n+1
3 . . . n+2
. .
. .
. .
m m+1 . . . n+m-1
Space complexity : O(mn). For each DFS we need O(h) space used by the system stack, where hh is the maximum depth of the recursion. In the worst case, O(h) =O(mn).
我不明白他们是如何得到这个时间复杂度或 space 复杂度的。对于 space 成本，我想最坏的情况是矩阵按行和列升序排序，但单个堆栈将大致与 mxn 正方形的对角线长度成正比。这就是为什么 space 是最坏情况与 O(mn) 成正比的原因吗？另外，space 的成本是 O(2^(m+n)) 而不是 O(4^(m*n)？
我相信 Sunny 是正确的，暴力搜索的时间复杂度为 O(4^(m*n))，其中 n 和 m 是矩阵中的行数和列数与给定数组关联。我想建议一个 O(n*m) 算法和实现它的 Ruby 代码。
在诸如此类的问题中，倾向于考虑从矩阵中的每个元素移动到所有相邻的较大值元素（最多 4 个），然后从这些元素中的每一个移动到它们所有相邻的较大值元素- 值元素，依此类推（因此为 O(4^m*n)）。但是，由于路径必须增加，我们可以用不同的方式来看待问题，从而开发出高效的优化算法。
假设我们按值对所有位置进行分组。对于问题中给出的示例，可以表示为：
value_to_locs
#=> { 9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]], 8=>[[1, 2]],
# 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
接下来让我们按降序考虑散列值：
to_process = value_to_locs.keys.sort.reverse
#=> [9, 8, 6, 4, 2, 1]
首先我们处理值为9的两个位置。从这两个位置开始的递增路径的长度显然是 1（路径是 [[0, 0]] 和 [[1, 0]]），因为无处可去。我们将此信息保存到一个先前为空的散列 processed，现在是：
processed = { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil } }
接下来考虑值为 8（to_process 的第二个元素）[1, 2] 的单个位置。如果从该位置开始的递增路径的长度大于 1，则它接下来必须转到 processed 的元素之一。 [1, 2] 既不与 [0, 0] 相邻，也不与 [1, 1] 相邻，因此我们添加键值对：
[1, 2]=>{ len: 1, next: nil }
到processed，获得
processed
#=> { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil },
# [1, 2]=>{ len: 1, next: nil } }
要检查的下一个值（在 to_process 中）是 6，它出现在两个位置，[1, 0] 和 [1, 1]。前者与 processed ([0, 0]) 中的一个位置相邻，因此我们将键值对
processed
[1, 0]=>{ len: 1 + processed[[0, 0]][:len], next: [0, 0] }
#=>{ len: 2, next: [0, 0] }
另一个值为6、[1, 1]的元素在processed、[0, 1]和[1, 2]中有两个相邻的元素，所以添加
[1, 1]=>{ len: 1 + processed[[0, 1]][:len], next: [0, 1] }
#=>{ len: 2, next: [0, 1] }
或
[1, 1]=>{ len: 1 + processed[[1, 2]][:len], next: [1, 2] }
#=>{ len: 2, next: [1, 2] }
到processed，即:len的值最大的那个。 （这里是平局，所以可以选择其中一个。）
以此类推，直到原数组的所有元素都是processed中的键。然后我们将processed[loc][:len]最大的位置loc作为最长递增路径的起点select，并重构相关路径。
请注意，密钥 :next 仅用于重建最长路径。如果只需要最长路径的长度，则不需要该密钥。
代码
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
value_to_locs.keys.sort.reverse.each do |x|
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
low, high = value_to_locs.keys.minmax
high.downto(low) do |x|
next unless value_to_locs.key?(x)
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def greater_neighbors((r,c), arr, row_indices, col_indices)
curr_val = arr[r][c]
[[-1,0], [1,0], [0,-1], [0, 1]].each_with_object([]) do |(rdelta, cdelta), a|
ra = r + rdelta
ca = c + cdelta
a << [ra, ca] if row_indices.cover?(ra) && col_indices.cover?(ca) &&
curr_val < arr[ra][ca]
end
end
def extract_path(processed)
loc, g = processed.max_by { |loc,g| g[:len] }
len = g[:len]
path = [loc]
loop do
break if g[:next].nil?
loc = g[:next]
path << loc
g = processed[loc]
end
[len, path]
end
例子
#1
arr = [
[9,9,4],
[6,6,8],
[2,1,1]
]
longest_increasing_path(arr)
#=> [4, [[2, 1], [2, 0], [1, 0], [0, 0]]]
#2
rows = 10
cols = 10
a = (1..9).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
#=> [[4, 7, 5, 3, 5, 4, 2, 2, 9, 3],
# [8, 3, 3, 5, 4, 2, 8, 1, 8, 3],
# [7, 1, 9, 4, 2, 7, 1, 4, 4, 6],
# [3, 7, 5, 5, 2, 3, 9, 1, 9, 7],
# [2, 6, 7, 1, 5, 9, 3, 5, 2, 9],
# [4, 4, 6, 7, 8, 4, 9, 7, 6, 1],
# [9, 7, 5, 4, 6, 8, 8, 4, 4, 8],
# [3, 1, 9, 9, 5, 7, 9, 6, 7, 2],
# [5, 6, 4, 8, 2, 3, 4, 3, 3, 9],
# [7, 9, 6, 9, 5, 2, 9, 7, 6, 3]]
require 'time'
t = Time.now
longest_increasing_path(arr)
#=> [5, [[6, 3], [6, 2], [5, 2], [5, 3], [5, 4]]]
Time.now - t
#=> 0.003606 seconds
因此，最长路径的长度为 5，包含元素 4，在 [6, 3]，然后左至 5，直至 6， 7 的权利，8 的权利。
#3
rows = 100
cols = 200
a = (1..20).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
t = Time.now
len, path = longest_increasing_path(arr)
#=> [12, [[86, 121], [86, 120], [86, 119], [87, 119], [87, 118], [86, 118],
# [85, 118], [85, 117], [86, 117], [87, 117], [88, 117], [89, 117]]]
Time.now - t
#=> 0.153562 seconds
path.map { |r,c| arr[r][c] }
#=> [1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 19, 20]
说明
首先让我们考虑示例#1 的辅助方法greater_neighbors。如图所示为arr，
row_indices = 0..arr.size-1
#=> 0..2
col_indices = 0..arr.first.size-1
#=> 0..2
接下来，（将 arr 视为矩阵）我们将具有相同值的位置分组：
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
#=> {9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]],
# 8=>[[1, 2]], 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
processed = {}
此散列将包含已检查的位置。
low, high = value_to_locs.keys.minmax
#=> [1, 9]
这提供了处理具有给定值的位置的顺序，从 high 到 low。
enum0 = high.downto(low)
#=> #<Enumerator: 9:downto(1)>
生成enum0的第一个元素并传递给块：
x = enum0.next
#=> 9
和
value_to_locs.key?(x)
#=> true
被执行了，所以我们不执行next.
我们现在考虑所有值为 9 的位置，然后是值为 8 的位置，依此类推。
生成9后传给block，next没有执行，进行如下计算：
b = value_to_locs[x]
#=> [[0, 0], [0, 1]]
enum1 = b.each
#=> #<Enumerator: [[0, 0], [0, 1]]:each>
loc = enum1.next
#=> [0, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
方法greater_neighbors简单地构造了一个数组，其中包含与loc相邻的所有位置，其值大于loc处的值。
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> nil
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>1, :next=>nil}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}}
我们现在生成 enum1 的下一个和最后一个元素并将其传递给块：
loc = enum1.next
#=> [0, 1]
此位置的计算与 [0, 0] 的计算类似，结果为：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil}}
我们到达了enum1的最后一个元素，所以我们接下来执行：
x = enum0.next
#=> 8
value_to_locs.key?(x)
#=> true # so next is not executed
b = value_to_locs[x]
#=> [[1, 2]]
enum1 = b.each
#=> #<Enumerator: [[1, 2]]:each>
loc = enum1.next
#=> [1, 2]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
同样，从这个位置无处可去，所以我们得到：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}}
继续，
x = enum0.next
#=> 7
value_to_locs.key?(x)
#=> false # so next is executed
x = enum0.next
#=> 6
value_to_locs.key?(x)
#=> true # so next is executed
b = value_to_locs[x]
#=> [[1, 0], [1, 1]]
enum1 = b.each
#=> #<Enumerator: [[1, 0], [1, 1]]:each>
loc = enum1.next
#=> [1, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> [[0, 0]]
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> [0, 0]
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>2, :next=>[0, 0]}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]}}
最后，我们来到了一个与更高价值的位置 ([0, 0]) 相邻的位置 ([1, 0])。
以这种方式继续计算，直到我们得到：
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]},
# [1, 1]=>{:len=>2, :next=>[0, 1]}, [0, 2]=>{:len=>2, :next=>[1, 2]},
# [2, 0]=>{:len=>3, :next=>[1, 0]}, [2, 1]=>{:len=>4, :next=>[2, 0]},
# [2, 2]=>{:len=>2, :next=>[1, 2]}}
剩下的就是找到k=>v最大的键值对k=>v，然后提取最长的路径。这是由助手 extract 完成的，它与 greater_neighbors 一样简单。