问题是这样的,给定一个长度数组说 N
, 我们必须找到长度为 W
的所有子序列这样那些 W
元素在排序时形成等差数列,间隔为 1。因此对于像 [1,4,6,3,5,2,7,9]
这样的数组, 和 W
作为 5,切片 [4,6,3,5,2]
可以被视为这样一个子序列,因为在排序时,它会产生 [2,3,4,5,6]
,公差为 1 的 A.P。
想到的直接解决方案是有一个滑动窗口,对于每个新元素,弹出旧元素,压入新元素,对窗口进行排序,如果对于那个窗口,window[w-1] - window[0] + 1 = w
,那么它就是这样一个子序列。但是,需要 O(NlogN)
时间,而解决方案位于 Codechef建议 O(N)
使用双端队列的时间算法。我很难理解该算法,正在推送和弹出的内容,为什么会这样,以及它如何按排序顺序维护窗口而不需要求助于每个新元素。谁能解释一下?
最佳答案
如果 max(segment) - min(segment) + 1 = W
,您观察到一个段有效是正确的.因此,问题简化为找到所有长度的最小值和最大值 W
O(N)
中的段.
为此,我们可以使用 deque D
.假设我们想找到最小值。我们将元素的索引存储在 D
中,假设基于 0 的索引。让A
是原始数组。
for i = 0 to N - 1:
if D.first() == i - W:
D.popFirst() <- this means that the element is too old,
so we no longer care about it
while not D.empty() and A[ D.last() ] >= A[i]:
D.popLast()
D.pushBack(i)
对于每个 i
,这将为您提供 [i - W + 1, i]
中的最小值作为索引 D.first()
处的元素.
popFirst()
从 D
中删除第一个元素.我们必须在 D
中的第一个元素时执行此操作大于W
离i
几步之遥,因为它不会对上述区间中的最小值做出贡献。
popLast()
从 D
中删除最后一个元素.我们这样做是为了维护排序顺序:如果 D
中的最后一个元素是大于 A[i]
的元素的索引, 然后添加 i
在 D
的末尾会破坏秩序。所以我们必须不断删除最后一个元素以确保 D
保持排序。
pushBack()
在 D
末尾添加一个元素.添加后,D
肯定会保持排序。
这是 O(1)
(要找到一个最小值,上面的伪代码是 O(n)
)因为每个元素都将被插入和弹出到/来自 D
最多一次。
这是有效的,因为 D
将始终是索引的滑动窗口,这些索引按其在 A
中的关联值排序.当我们遇到一个会破坏这个顺序的元素时,我们可以从 D
中弹出元素。 (滑动窗口)直到订单恢复。由于新元素比我们弹出的元素小,因此这些元素无法为解决方案做出贡献。
请注意,即使没有我使用的方法,您也可以通过保持与 D
关联的两个指针来实现这一点。 : start
和 end
.然后制作D
长度为 N
的数组你就完成了。
关于algorithm - 查找以随意方式存储的连续增加的子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12598260/