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

Я читаю эту статью здесь: 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.

Источник

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

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

Источник

Это магия монотонных функций и то понимание, которое можно получить, визуализируя пространство решения проблемы и то, как эти значения выравниваются. Давайте нарисуем один из примеров на странице, на которую вы ссылаетесь; индексы массива по оси 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 является показателем того, что мы находимся на самом низком левом значении, и так как мы впервые исследуем движение вдоль rs, мы гарантированно не пропустили ранее l за любой интервал в нашем поиске. Ясно, что мы перебираем слева направо, самое большее, по всем rи все lс, так O(n),

Источник
Другие вопросы по тегам