1

问题是这样的，给定一个长度为 的数组N，我们必须找到所有长度的子序列，W使得这些元素在排序时形成一个间隔为 1 的算术级数。所以对于像和5W这样的数组，切片可以是被认为是一个这样的子序列，因为在排序时，它产生，一个具有共同差为 1 的 AP。[1,4,6,3,5,2,7,9]W[4,6,3,5,2][2,3,4,5,6]

想到的直接解决方案是有一个滑动窗口，对于每个新元素，弹出旧元素，推送新元素，对窗口进行排序，如果对于那个窗口，window[w-1] - window[0] + 1 = w那么它就是这样一个子序列。但是，这需要O(NlogN)时间，而Codechef的解决方案提出了O(N)一种使用双端队列的时间算法。我很难理解算法，什么被推送和弹出，为什么会这样，以及它如何以排序顺序维护窗口而不需要使用每个新元素。谁能解释一下？

4

1 回答 1

1

你是正确的观察到一个段是有效的 if 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)

对于每个，这将为您提供作为 index 元素i的最小值。[i - W + 1, i]D.first()

popFirst()从 中删除第一个元素D。当 中的第一个元素距离D超过步时，我们必须这样做，因为它不会对上述区间中的最小值做出贡献。Wi

popLast()从 中删除最后一个元素D。我们这样做是为了保持排序顺序：如果 in 的最后一个元素D是大于 的元素的索引A[i]，那么i在末尾添加D会破坏顺序。所以我们必须不断删除最后一个元素以确保D保持排序。

pushBack()在末尾添加一个元素D。添加后，D肯定会保持排序。

这是O(1)（要找到一个最小值，上面的伪代码是O(n)），因为每个元素最多会被推送和弹出D一次。

这是有效的，因为D它将始终是一个按其关联值排序的索引的滑动窗口A。当我们在一个会破坏这个顺序的元素处时，我们可以从D（滑动窗口）弹出元素，直到恢复顺序。由于新元素比我们弹出的元素小，因此这些元素无法为解决方案做出贡献。

请注意，即使没有我使用的方法，您也可以通过保持两个与D:start和. 关联的指针来实现这一点end。然后制作D一个长度数组，N你就完成了。

于 2012-09-26T09:34:47.647 回答