algorithm - 查找以随意方式存储的连续增加的子序列

Question

问题是这样的，给定一个长度数组说 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)使用双端队列的时间算法。我很难理解该算法，正在推送和弹出的内容，为什么会这样，以及它如何按排序顺序维护窗口而不需要求助于每个新元素。谁能解释一下？

Answer 1

如果 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 的数组你就完成了。