algorithm - 如何使用范围最小查询实现二进制搜索？

Question

给定一个区间 A[ij]，我们可以使用 RMQ 轻松找出区间 A[ij] 之间的最小值。现在我正在尝试反转条件：- 给定最小值，找出包含该数字作为最小数字的间隔（最大长度）。我试图使用二进制搜索来实现这一点，但没有这样做。请帮我解释如何解决这个问题。谢谢你 。！！

Answer 1

这是一个简单的算法，它在线性时间内从数组的每个元素计算最接近左侧的较小数字。这个想法是维护一堆对（元素，位置）并在元素不再有用时弹出元素。伪代码：

stack = new Stack<Pair>() // an empty stack of pairs(element, position)
leftSmaller = new int[n] // an array to store the answer
fill(leftSmaller, -1) 
for (i = 0; i < n; i++) // n is the size of the given array
    while (!stack.isEmpty() and stack.top().first >= array[i]) // pop the elements from the stack while they are larger the current element
        stack.pop()
    if (!stack.isEmpty()) // if there is a smaller element 
        leftSmaller[i] = stack.top().second // its position is the answer for the current position
    stack.push(new Pair(array[i], i))

每个元素只被压入堆栈一次，最多弹出一次。这就是时间复杂度为 的原因O(n)。

它与您的问题中所述的问题有什么关系？您可以为数组中的每个位置预先计算左侧的第一个较小元素，右侧的第一个较小元素（通过在反转数组上运行此算法）。该职位的答案i是rightSmaller[i] - leftSmaller[i] - 1。在知道数组中每个位置的答案后，您可以轻松解决原始问题（对于给定的最小值，只需在所有i这些中选择最佳答案array[i] = minimum），