На практическом собеседовании запрашивается максимальное значение ji при условии, что array [j]> = array [i];не понимаю решение

Question

Я читаю эту статью здесь: https://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/, и я не могу понять объяснение того, как работает решение O (n).Параграф, описывающий это, кажется, противоречит кодексу.Я просмотрел образец массива и вручную убедился, что это работает, но мне это не кажется интуитивно понятным.

Желает ли кто-то более опытный в решении задач программирования объяснить, как и почему это работает?, или объясните, что с ним не так?

Спасибо.

(Ниже текст по ссылке выше:)

Проблема:

Учитываямассив arr [], найдите максимум j - i такой, что arr [j]> arr [i]. Для данного массива arr [] найдите максимум j - i такой, что arr [j]> arr [i].

Примеры:

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6  (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Метод 2 (Эффективный)

Чтобы решить эту проблему, нам нужно получить два оптимальных индекса arr []: левый индекс i и правый индекс j.Для элемента arr [i] нам не нужно рассматривать arr [i] для левого индекса, если в левой части arr [i] есть элемент меньше, чем arr [i].Аналогично, если в правой части arr [j] есть больший элемент, нам не нужно рассматривать этот j для правильного индекса.Таким образом, мы строим два вспомогательных массива LMin [] и RMax [] так, чтобы LMin [i] содержал наименьший элемент в левой части arr [i], включая arr [i], а RMax [j] содержал наибольший элемент в правой частиarr [j], включая arr [j].После построения этих двух вспомогательных массивов мы пересекаем оба этих массива слева направо.Обходя LMin [] и RMa [], если мы видим, что LMin [i] больше, чем RMax [j], то мы должны двигаться вперед в LMin [] (или сделать i ++), потому что все элементы слева от LMin [i]больше или равно LMin [i].В противном случае мы должны двигаться вперед в RMax [j], чтобы найти большее значение j - i.

Answer 1

Это магия монотонных функций и вид понимания, которое можно получить, визуализируя пространство решения проблемы и то, как эти значения совмещаются. Давайте нарисуем один из примеров на странице, на которую вы ссылаетесь; индексы массива по оси x, LMin и RMax по оси y:

  {34, 8,10, 3, 2,80,30,33, 1}
    0  1  2  3  4  5  6  7  8

80  r  r  r  r  r  r
 .
34  l
33                    r  r
 .                       ^
30
 .
10
 . 
 8     l  l
 .     ^
 3           l
 2              l  l  l  l
 1                         lr
    0  1  2  3  4  5  6  7  8

Значение r не является (обязательно) значением, связанным с индексом массива; скорее это показатель того, насколько далеко мы можем увеличить интервал вправо, гарантируя, что * r справа не будет больше (это означает, что мы могли бы пропустить больший интервал). Точно так же, l является показателем того, что мы находимся на самом низком левом значении, и, поскольку мы впервые исследуем движение вдоль r с, мы гарантированно не пропустили более раннюю l для любого интервала в нашем поиск. Ясно, что мы выполняем итерацию слева направо не более чем по всем r с и всем l с, поэтому O(n).

Answer 2

Работает.Автор кода только что запутался.

Как указывает редакция, учитывая индексы i1 < i2 с arr[i1] ≤ arr[i2], нет смысла рассматривать i = i2.Мы всегда можем добиться большего успеха, установив вместо этого i = i1, поскольку для всех j,

1. j - i1 > j - i2 и
2. , если arr[j] > arr[i2], то факт, что arr[i2] ≥ arr[i1] подразумевает, что arr[j] > arr[i1].

Точно так же, учитывая индексы j1 < j2 с arr[j1] ≤ arr[j2], нет смысла рассматривать j = j1.

Давайте рассмотрим первый пример ввода иисключите всех этих неоптимальных кандидатов.

34  8  10  3  2  80  30  33  1
34  8      3  2              1  // candidate values of arr[i]
                 80      33  1  // candidate values of arr[j]

Обратите внимание, что обе подпоследовательности уменьшаются.Это прямое следствие вышеприведенных условий для того, чтобы быть кандидатом.

Поиск лучших i и j теперь включает в себя клише конкурса программ.Позвольте мне организовать возможности в таблице. Обратите внимание, что алгоритм не создает эту таблицу явно;это всего лишь наглядное пособие.

    80  33  1
-------------
34   √
 8   √   √
 3   √   √
 2   √   √
 1   √   √

Галочка (√) означает, что arr[i] < arr[j].Понижение означает увеличение i и уменьшение arr[i].Движение влево означает уменьшение j и увеличение arr[j].Следовательно, везде, где есть галочка, все квадраты ниже или слева или какая-то комбинация также имеют галочки.С другой стороны, учитывая квадрат с галочкой, который находится ниже / слева от другого квадрата с галочкой, последний квадрат обязательно является лучшим решением, потому что i меньше или j больше или оба.Поэтому нас очень интересует граница между галочками и отсутствием галочек, потому что именно в этом заключается оптимальное решение.

Алгоритм отслеживания границы прост.Начните с верхнего левого квадрата.Если у текущего квадрата есть галочка, идите направо.Иначе иди вниз.Я надеюсь, что вы сможете понять, как этот процесс посещает первую галочку в каждом столбце за время O(#rows + #columns).Вот еще одна возможная таблица.

    33  8  7  3
---------------
34
 8   √
 3   √  √  √
 2   √  √  √  √
 1   √  √  √  √

Чтобы перейти к реализации, обратите внимание, что мы выполняем тот же поиск, но с некоторыми дублированными строками / столбцами, чтобы заполнить пустое пространство, оставленное не кандидатами,избавляя нас от необходимости следить за соответствием между индексами.Это в основном та же идея.