查找长度W其中包含可以被布置在连续的序列号的子阵列。为前{4,5,1,5,7,6,8,4,1}，W是5，输出可以是 - {5,7,6,8,4}。

Find the subarray of length W which consists of numbers that can be arranged in a continuous sequence. For ex- {4,5,1,5,7,6,8,4,1} and W is 5, output can be -{5,7,6,8,4}..

推荐答案

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

A contiguous subarray of length W, containing a continuous (but unsorted) sequence, has three properties that can be used to construct an efficient algorithm:

有子数组中W¯¯元素。 在子阵最大和最小数之间的差异是 W-1 。 有子数组中重复元素。

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

Algorithm should advance two pointers to input array and check if the subarray between these pointers satisfies these three properties.

在推进两个指针，以保持指针等于W之间的区别。 在推进的第一个指针，把相应的数组元素为一组（控制式两份），并以最小 - 最大队列（控制数的范围）。 如果一个重复的是在该组中，推进第二指针，以第一这些重复元素，更新两个集和队列的位置上。 在推进第二指针，而最大值和最小值之差保持大于 W-1 ，删除相应的无论从集和队列中的元素。 当所有三个属性为true停止。 Advance both pointers to keep difference between pointers equal to W. While advancing the first pointer, put corresponding array element to a set (to control duplicates) and to a min-max queue (to control range of numbers). If a duplicate is found in the set, advance second pointer to position of first of these duplicate elements, updating both the set and the queue. Advance second pointer while difference between max and min values keeps greater than W-1, remove corresponding elements from both the set and the queue. Stop when all three properties are true.

一个最小 - 最大队列可以实现为一对最小 - 最大栈，在这个答案描述。一组可以被实现或者作为一个散列组（给予为O（n）的算法预期的复杂性），或作为二进制搜索树（给出为O（n日志（n））的最坏情况的复杂性），或作为一个组合位集合和一个ringbuffer - 只保留比特，对应于元素是最大值和最小值之间，所报告的队列（给出为O（n）最坏情况的复杂性）

A min-max queue may be implemented as a pair of min-max stacks, described in this answer. A set may be implemented either as a hash set (giving O(n) expected complexity for the algorithm), or as a binary search tree (giving O(n log(n)) worst case complexity), or as a combination of a bitset and a ringbuffer - to keep only bits, corresponding to elements that are between min and max values, reported by queue (giving O(n) worst case complexity).

例输入数组{42,10,7,4,5,1,5,7,6,8,4,1}和W = 5（：标志开始ringbuffer的）。

Example for input array {42,10,7,4,5,1,5,7,6,8,4,1} and W=5 (":" marks start of the ringbuffer).

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)