arrays - 由可以连续排列的数字组成的子数组。

Question

找到长度为 W 的子数组，它由可以连续排列的数字组成。例如 - {4,5,1,5,7,6,8,4,1} 且 W 为 5，输出可以是 -{5,7,6,8,4}..

Answer 1

一个长度为 W 的连续子数组，包含一个连续（但未排序）的序列，具有三个可用于构造有效算法的属性：

1. 子数组中有 W 个元素。
2. 子数组中的最大和最小数字之间的差异是W-1。
3. 子数组中没有重复的元素。

算法应该将两个指针提前到输入数组，并检查这些指针之间的子数组是否满足这三个属性。

1. 推进两个指针以保持指针之间的差异等于 W。
2. 在推进第一个指针的同时，将相应的数组元素放入一个集合（以控制重复项）和一个最小-最大队列（以控制数字范围）。
3. 如果在集合中找到重复项，则将第二个指针前进到这些重复元素中的第一个的位置，同时更新集合和队列。
4. 推进第二个指针，同时最大值和最小值之间的差值保持大于W-1，从集合和队列中删除相应的元素。
5. 当所有三个属性都为真时停止。

最小最大队列可以实现为一对最小最大堆栈，如本答案中所述。集合可以实现为散列集（给出算法的 O(n) 预期复杂度），或二叉搜索树（给出 O(n log(n)) 最坏情况复杂度），或者作为bitset 和 ringbuffer - 只保留位，对应于最小值和最大值之间的元素，由队列报告（给出 O(n) 最坏情况复杂度）。

输入数组 {42,10,7,4,5,1,5,7,6,8,4,1} 和 W=5 的示例（“：”标记环形缓冲区的开始）。

subarray       bitset        rb_start     min  max
42             :1 0 0 0 0    42           42   42
10             :1 0 0 0 0    10           10   10 (with 42, max-min>W-1)
10 7            1 0:1 0 0    7            7    10
7 4             0 0 1 0:1    4            4    7  (with 10, max-min>W-1)
7 4 5           1 0 1 0:1    4            4    7
4 5 1           1:1 0 0 1    1            1    5  (with 7, max-min>W-1)
1 5             1:1 0 0 0    1            1    5  (5 is a duplicate)
5 7            :1 0 1 0 0    5            5    7  (with 1, max-min>W-1)
5 7 6          :1 1 1 0 0    5            5    7
5 7 6 8        :1 1 1 1 0    5            5    8
5 7 6 8 4       1 1 1 1:1    4            4    8  (success)