algorithm - 範囲最小クエリでバイナリ検索を実装する方法は?

Question

A[ij] という間隔が与えられた場合、RMQ を使用して、間隔 A[ij] 間の最小値を簡単に見つけることができます。今、私は条件を逆にしようとしています:- 最小値が与えられた場合、この数値を最小値として含む間隔 (最大長) を見つけます。Binary Search を使用してこれを実装しようとしましたが、失敗しました。この問題にアプローチする方法を説明するのを手伝ってください。ありがとうございました 。!!

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))

各要素は 1 回だけスタックにプッシュされ、多くても 1 回ポップされます。そのため、時間複雑度はO(n)です。

質問に記載されている問題とどのように関連していますか? 配列内の各位置の左側の最初の小さい要素、右側の最初の小さい要素を事前計算できます (このアルゴリズムを逆配列で実行することにより)。ポジションの答えiは ですrightSmaller[i] - leftSmaller[i] - 1。配列内の各位置の答えがわかれば、元の問題を簡単に解決できます (特定の最小値について、そのiようなすべての中から最適な答えを選択するだけですarray[i] = minimum)。