algorithm - 找到最大的连续间隔，使得开始和结束之间的所有数字都大于开始并且小于结束

Question

你给了整数数组

例如 5,3,4,3,9,4,4,6,8,6,5,7

你必须找到最大的间隔 (i,j)，使得 i 和 j 之间的所有数字都大于等于 i 处的数字但小于等于 j 处的数字。数字不需要按排序顺序。i 处的数字也应小于 j 处的数字。

在上面的例子中有两个这样的间隔 3,4,3,9 和 4,4,6,8

在 3,4,3,9 - 中间两个数字 (4,3) 大于等于起始数字 (3) 但小于等于结束数字 (9) 。起始编号 (3) 也小于结束编号 (9)。

在 4,4,6,8 - 中间两个数字 (4,6) 大于等于起始数字 (4) 但小于等于结束数字 (8)。起始编号（4）也小于结束编号（8）。

解决这个问题的一种方法是检查所有大小为 n 的区间，然后是大小 n-1 ，依此类推，直到我们得到这样的区间。但我希望通过划分或征服/DP/或其他一些方法来实现高效的算法

标签： algorithm

Answer 1

我们可以O(n log n)通过将每个元素视为区间中潜在的最左侧元素来解决这个问题。对于每个这样的候选者，（1）找到右边的第一个元素低于它 - 这是可能间隔的右侧边界，因为包含这样的元素会使约束无效；(2) 找到区间中最大元素的最左侧实例（如果A[j]允许等于其左侧的元素，则找到最右侧的实例）——这是区间可以在不使约束无效的情况下扩展的最右侧。

O(n)我们可以使用堆栈为 中的所有元素存储 (1) 的答案。我们可以为 range-maximum-query 预处理一个结构，该结构将及时回答 (2) 的第一部分O(log n)。一旦找到区间的最大值，如果我们在数组中有一个其实例的有序列表（我们可以O(n)使用哈希表对其进行预处理），我们可以在O(log n)时间区间中找到它最右边或最左边的出现。