查找数组中可能的序列数,以及其他条件

Question

有一个序列{a1,a2,a3,a4,..... aN}.运行是序列的最大严格增加或严格减少的连续部分.例如.如果我们有一个序列{1,2,3,4,7,6,5,2,3,4,1,2}我们有5个可能的运行{1,2,3,4,7},{7, 6,5,2},{2,3,4},{4,1}和{1,2}.

给定四个数字N,M,K,L.计算具有正好M次运行的N个数的可能序列的数量,序列中的每个数字小于或等于K并且相邻数字之间的差异小于等于到L.

在一次采访中提出了这个问题.

我只能想到一个强力解决方案.什么是这个问题的有效解决方案？

Answer 1

我想你所说的“强力解决方案”是什么意思，我所说的“涉及 N、M、K、L 上的嵌套循环的直接解决方案”是什么意思？有时，简单的解决方案就足够了。有时，当您没有更好的解决方案时，直接的解决方案就足够好了。另一种情况是数字不是很大的时候。

有了这个，我会以相反的方向写循环，或者类似的东西。我是说：

1. 创建 2 个辅助数据结构，一个包含 <=K 的数字的索引，一个包含与其邻居的差值 <=L 的数字的索引。
2. 遍历数字列表并填充前述辅助数据结构。
3. 找到这两个数据结构中值的交集；这些将是开始搜索跑步的有趣地点的索引。
4. 看看每个有趣的地方。

除非有人证明这是最有效的解决方案。