arrays - 查找需要从数组中删除的元素，使得 2*min>max

Question

考虑以下问题:

An array of integers is given. Your goal is to trim the array such that 2*min > max, where min and max are the minimum and maximum elements of the array. You can remove elements either from start or from end of the array if above condition does not meet. The number of removals should be minimized.

例如如果数组是

a, b, c, d, e, f

其中 c 是最小值，e 是最大值，那么如果 2*c > e 为真，我们就完成了。如果不是，我们可以从开头(即 a、b、c)或从结尾(即 e、f)删除，这样新的最小值或最大值将满足条件并且删除应该是最小的。

我有一个 O(n²) 算法来解决这个问题。这能在 O(n log n) 时间内解决吗？

Answer 1

注意问题是找到满足条件的最大子数组。意识到如果条件适用于索引区间，它也适用于其中包含的所有区间。所以如果我们固定一个边界，我们可以贪婪地选择另一个边界尽可能远离它。

有可能在线性时间内解决这个问题:

如果选择元素 i 作为左边界，则将 r_i 定义为可能的最右边界。我们可以证明 r 在 i 中是单调的，因此我们可以维护两个指向 i 和 r_i 并在每次将 i 递增 1 后尽可能递增 r_i 。两个指针总共递增 O(n) 次，我们可以使用范围内值的堆或二叉搜索树在每次递增时将范围最小值/最大值保持在 O(log n) 中。

使用 monotonic queue我们可以在 O(1) 中维护极值并获得 O(n) 的总运行时间。可以找到队列的另一个 C++ 实现 here ，例如。

---

另一种不太优雅的方法是使用 RMQ data structure .它让你在 O(n log n) 预处理后查询 O(1) 范围内的最小值/最大值(O(n) 预处理也是可能的，但这里复杂且不必要，因为算法的其余部分不是线性时间).

现在修复左边框(有 n 种可能性)。使用二进制搜索找到仍然满足条件的最右边界(您可以检查 O(1) 是否满足)。

这是可行的，因为谓词“范围满足条件”在包含方面是单调的(如果一个范围满足它，则包含在其中的所有范围也满足它)。