Цель — найти максимальную разницу индексов j - i в массиве, где j > i и arr[j] > arr[i]. Наивный подход "в лоб" проверяет все пары за O(n²) времени, что неэффективно для больших входных данных.
Более эффективное решение работает за O(n) времени, используя предвычисленные вспомогательные массивы:
left_min[i] — хранит минимальное значение от начала до индекса iright_max[j] — хранит максимальное значение от индекса j до концаЭто позволяет использовать технику двух указателей для поиска максимальной подходящей разницы без вложенных циклов.
def max_index_diff(arr):
n = len(arr)
left_min = [0] * n
right_max = [0] * n
left_min[0] = arr[0]
for i in range(1, n):
left_min[i] = min(left_min[i - 1], arr[i])
right_max[n - 1] = arr[n - 1]
for j in range(n - 2, -1, -1):
right_max[j] = max(right_max[j + 1], arr[j])
i, j, max_diff = 0, 0, -1
while i < n and j < n:
if left_min[i] <= right_max[j]:
max_diff = max(max_diff, j - i)
j += 1
else:
i += 1
return max_diff
left_min гарантирует, что мы всегда рассматриваем наименьшее возможное значение слеваright_max гарантирует, что мы всегда рассматриваем наибольшее возможное значение справаO(n) — три линейных проходаO(n) — для двух вспомогательных массивовМассив left_min хранит минимальное значение, встреченное от начала массива до каждого индекса i включительно.
Новый — ещё не проверен сообществом
Вы