移动 window RMQ 性能改进

Question

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

我要查找的是范围 [0, L-1], [1,L], [2,L+1]...[N-L,N-1] 中的最小值

（就像从左到右移动window长度L）

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

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

总计为 O(N lg N)。

我想知道是否有任何算法可以在满足以下要求的情况下实现比这更好的算法：

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

我对 RMQ 做了一些研究，我发现最接近的方法是使用稀疏 table，它实现了 O(1) 查询时间和 O(N lg N) 预处理时间。 reduce RMQ to LCA问题的另一种方法可以满足要求，但需要对数组A.

进行一些限制

那有没有可能在A没有限制的情况下解决我的问题就可以满足要求呢？

Answer 1

是的，使用 deque。我们将保持元素按升序排序，因此对于当前位置 i，第一个元素始终是 [i - L + 1, 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)。

移动 window RMQ 性能改进

Moving window RMQ performance improvement

c++

algorithm

rmq