Как реализовать бинарный поиск с минимальным диапазоном запросов?

Question

Учитывая интервал, скажем, A[ij], мы можем легко определить минимальное значение между интервалом A[ij], используя RMQ. Теперь я пытаюсь изменить Условие:- Учитывая минимум, определите интервал (максимальная длина), который содержит это число в качестве минимального числа. Я пытался реализовать это с помощью бинарного поиска, но не смог. Пожалуйста, помогите мне объяснить, как подойти к этой проблеме. Благодарю вас.!!

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