这里有两种解决问题的方法，一种易于编码，另一种更复杂，但我希望它应该更快，可能更快。两者都使用以下数组进行演示。
a1 = [1,1,2,3,4]
a2 = [1,1,2,2,4,4,5,5,5]
a3 = [1,1,3,2,4,4,5,5,7,6,5,6,5,4,3,4,5,7,8]
代码不多，但可能足够快
def quick_n_dirty(arr)
arr.size.downto(1).each do |n|
arr.each_index.each_cons(n) do |a|
mn, mx = a.map { |i| arr[i] }.minmax
return { start: a.first, end: a.last } if mx <= mn + 1
end
end
end
quick_n_dirty(a1)
#=> {:start=>0, :end=>2}
quick_n_dirty(a2)
#=> {:start=>4, :end=>8}
quick_n_dirty(a3)
#=> {:start=>4, :end=>7}
请参阅Enumerable#each_cons。
考虑a1，它包含五个元素。先看看整个数组是否满足要求，这样我们就完蛋了：
enum = a1.each_cons(5)
#=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(5)>
要查看将生成的元素，enum我们可以将其转换为数组：
enum.to_a
#=> [[1, 1, 2, 3, 4]]
它本身只生成一个元素a1：
a = enum.next
#=> [1, 1, 2, 3, 4]
b, c = a.minmax
#=> [1, 4]
正如我们看到的那样，(c-b).abs = 3不符合要求。现在考虑所有大小为 的子数组。如果发现一个具有所需的属性，我们就完成了。3 > 1a14
enum = a1.each_cons(4)
#=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(4)>
enum.to_a
#=> [[1, 1, 2, 3], [1, 2, 3, 4]]
a = enum.map { |arr| arr.minmax }
#=> [[1, 3], [1, 4]]
b = a.map { |x,y| (y-x).abs }
#=> [2, 3]
b.find { |diff| diff <= 1 }
#=> nil
这告诉我们没有4满足要求的大小子数组，因此我们继续查看大小子数组3：
enum = a1.each_cons(3)
#=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(3)>
enum.to_a
#=> [1, 1, 2], [1, 2, 3], [2, 3, 4]]
a = enum.map { |arr| arr.minmax }
#=> [[1, 2], [1, 3], [2, 4]]
b = a.map { |x,y| (y-x).abs }
#=> [1, 2, 2]
b.find { |diff| diff <= 1 }
#=> 1
支付污垢！我们发现子数组[1, 1, 2]符合要求，所以我们完成了！
这就是我的代码所做的，除了它返回一个散列，显示具有所需属性的最大子数组（或者我应该说“a”，而不是“the”，因为可能存在关联）的开头和结尾。（在重新阅读问题时，似乎只需要最大子数组的长度，允许进行小幅简化。）
如果n = arr.size，在最坏的情况下，必须检查的子数组的数量等于n + (n-1) + (n-2) + ... + 2 + 1，等于n*(n+1)/2。
更多代码，但应该更快
def should_be_faster(arr)
a = arr + [Float::INFINITY]
current = { early: 0, late: nil }
a.each_with_index.with_object({ start: 0, end: 0 }) do |(n,i), longest|
next if i.zero?
curr_val = a[i]
curr_early_val = a[current[:early]]
curr_late_val = current[:late].nil? ? nil : a[current[:late]]
if current[:late].nil?
case curr_val - curr_early_val
when 0
when 1, -1
current[:late] = i
else
update_if_improvement(current, longest, i)
current[:early] = i
current[:late] = nil
end
elsif curr_val != curr_early_val && curr_val != curr_late_val
update_if_improvement(current, longest, i)
if (curr_val - curr_late_val).abs == 1
current[:early] = current[:late]
current[:late] = i
else
current[:early] = i
current[:late] = nil
end
end
end
end
def update_if_improvement(current, longest, i)
if i - current[:early] > longest[:end] - longest[:start] + 1
longest[:start] = current[:early]
longest[:end] = i-1
end
end
should_be_faster(a1)
#=> {:start=>0, :end=>2}
should_be_faster(a2)
#=> {:start=>4, :end=>8}
should_be_faster(a3)
#=> {:start=>4, :end=>7}