Это проблема leetcode, в которой нам дан несортированный массив целых чисел, который действует как стены на земле с индексами массива, указывающими их положение по отношению друг к другу.
См. leetcode для более подробного описания проблемы.
Теперь моей первой мыслью было взять два индекса i , j , которые представляют две предложенные граничные линии.
Теперь, если i+1 элемент массива больше i и j-1 элемент больше j . Тогда, безусловно, вы можете обесценить i и j. Каким бы способом вы ни заливали воду, она всегда будет ограничена двумя большими перемычками.
так что в этом случае
площадь (i, j) = max (площадь (i + 1, j-1), площадь (j-1, j), площадь (i, i + 1))
аналогично, если оба этих следующих бара меньше, чем i & j . Ясно, что границу i и j можно включить в максимальную площадь
площадь (i, j) = площадь (i + 1, j-1) + площадь (j-1, j) + площадь (i, i + 1)
Если одна полоса меньше другой
are(i,j) = max(площадь(i,i+1), площадь(i+1,j))
и наоборот для другого случая
Теперь это занимает n2 времени, что дало мне результат превышения TTL.
Задача требует N раз
поэтому задача потребовала O(n) времени
Алгоритм:
инициализировать индексы для первого и последнего элемента массива
если первый элемент больше последнего элемента, вам больше не нужен последний элемент, поэтому вы уменьшаете последний индекс
иначе увеличить первый индекс
Алгоритм довольно упрощен, и кажется, что он пропустит один или два случая, но оказывается, что алгоритм довольно упрощен.
