c++ - 移动窗口 RMQ 性能改进

Question

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

我要查找的是范围 [0, L-1]、[1,L]、[2,L+1]...[N-L,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(lgN)
3. 对所有可能的范围重复步骤 2，每次迭代移动到下一个元素。 O(N)

总数是 O(N lg N)。

---

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

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

我对 RMQ 做了一些研究，我发现最接近的方法是使用稀疏表，它实现了 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)。