1

A假设我有一个长度为整数的数组N，我也有一个整数L<= N。

我试图找到的是范围 [0, L-1], [1,L], [2,L+1]....[NL,N-1] 的最小值

L（就像一个从左到右移动长度的窗口）

我的算法现在是 O(N lg N) 和 O(N lg N) 预处理：

  1. 将所有号码保存A[0...L-1]在多组S中，并将号码按顺序存储在队列Q中。[0, L-1] 的最小值只是 的第一个元素S。O(N lg N)
  2. 弹出 的第一个元素Q，在里面找到这个元素S并删除。然后推A[L]入S。[1, L] 的最小值只是 的第一个元素S。O(lg N)
  3. 对所有可能的范围重复步骤 2，每次迭代移动到下一个元素。上）

总计为 O(N lg N)。

我想知道是否有任何算法可以达到比这更好的以下要求：

  1. 预处理时间（如果需要）为 O(N)
  2. 查询时间如果 O(1)

我对 RMQ 进行了一些研究，我发现最近的方法是使用稀疏表，它实现 O(1) 查询时间但 O(N lg N) 预处理时间。另一种将RMQ简化为LCA问题的方法可以满足要求，但需要对数组进行一些限制A。

那么在解决我的问题时，是否有可能在没有限制A的情况下满足要求？

4

1 回答 1

3

是的，使用deque。我们将保持元素升序排序，因此第一个元素始终是[i - L + 1, i]当前位置的最小值i。我们不会保留实际元素，而是保留它们的位置。

d = empty deque
for i = 0 to n-1:

    // get rid of too old elements
    while !d.empty && i - d.front + 1 > L:
        d.pop_front()

    // keep the deque sorted
    while !d.empty && A[d.back] > A[i]        
        d.pop_back()

    d.push_back(i)
    // A[d.front] is the minimum in `[i - L + 1, i]

由于每个元素最多进入和离开双端队列一次，因此这是O(n).

于 2017-02-09T15:09:31.607 回答