任意范围内两个数组最小值的最大值查找算法

Question

假设我们有两个长度相等的整数数组a_1, ..., a_n和b_1, ..., b_n。对于任何给定的索引对i和j，其中1 <= i < j <= n，我们需要找到形式为a_k, ..., a_{l-1}, b_l, ..., b_{j-i+k}的任意序列的最小值的最大值，其中0 <= k <= n-j+i且l可以是j-i+k+1，即该序列完全来自数组a。当k = 0时，该序列完全来自数组b。

我们希望以非常高效的方式为所有i和j对执行此操作。

例如，给定

`a=[3,2,4,1]` and `b=[4,6,1,3]`
when `i=1, j=3`, the sequence can be
`[3,2,4]`, min is 2
`[3,2,1]`, min is 1
`[3,6,1]`, min is 1
`[2,4,1]`, min is 1
`[2,4,3]`, min is 2
`[2,1,3]`, min is 1
`[4,6,1]`, min is 1
`[6,1,3]`, min is 1

对于这个输入，最大值为2。

有没有一种有效的方法来运行它？

- Qiang Li

---

这似乎只取决于j-i，而不是分别取决于i和j。 - user31264

当k=0时，序列从a_0开始，但是你的索引从1开始。 - user31264

按照惯例，k=0 表示在所选序列中没有从 a 中选择的元素。 :) - Qiang Li

这看起来很有趣，但我不理解问题。您能否（半）正式地定义确切的预期输入和输出是什么？并且请提供一个示例，其中每个数组都包含不同的数字。（首先，我甚至不理解a_k和a_l是什么，以及如果k = 0，则我们不包括a_0；然后，我也困惑于我们一次是否只给出一对(i,j)，还是我们应该处理所有(i,j)，以及如何作为解决方案。） - גלעד ברקן

Answer 1

看起来可以让暴力算法运行得相当快。

如果你将每个序列预处理成一个平衡树，其中每个节点都带有该子树的最小值，那么您可以通过在适当的位置分割树，在O(log n)时间内找到该序列任何子范围的最小值。例如，有关更多信息，请参见this paper。请注意，此预处理需要O(n)时间。

我们将区间（i，j）称为窗口。这个问题的复杂度不取决于特定的（i，j），而是窗口的大小（即，j-i+1）。对于窗口大小为m（= j-i+1），有n-m+1个该大小的窗口。对于每个窗口，有m + 1个位置可以“切割”窗口，以便一些元素的前缀来自序列a，后缀来自序列b。您需要为每个切割付出O(log n)的代价（如上所述拆分二叉树）。总成本为O((n-m+1) * (m+1) * log(n))。

可能有更快的方法，可以通过重用分割或者注意到相邻的窗口共享许多元素来实现。但无论如何，我认为上面提到的二叉树分割技巧可能会有帮助！

- Sam Westrick

---

这个 O((n-m+1) * (m+1) * log(n)) 不够快。需要更快的，例如 O(n log(n))。 - Qiang Li