Слепой 75 — Вопросы по программированию и техническому собеседованию — серия пояснений

Проблема:

Ограничения:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

Объяснение:

Это отличный вопрос для массива, для которого можно использовать левый и правый указатели. Начиная с крайнего левого и крайнего правого, вы можете использовать цикл, чтобы определить, следует ли уменьшить правый указатель или увеличить левый указатель. Все это if-утверждение, если левое меньше правого, зачем нам уменьшать правое, мы должны увеличивать левое. В противном случае уменьшите право. Затем для каждой итерации цикла вычисляйте площадь и отслеживайте наибольшую возвращаемую площадь. Довольно простой вопрос, который отлично подходит для изучения того, как использовать указатели для получения ответов с меньшей временной сложностью.

Решение указателя — O (n):

Как сказано, инициализируем указатели и устанавливаем ответ равным 0. Пока левая меньше правой (иначе мы получили бы отрицательную площадь), определяем площадь и нужно ли увеличивать левую или уменьшать правую. Мы устанавливаем ответ на максимальное значение самого себя, а затем расчет площади. Вычисление площади представляет собой произведение ширины (справа минус лево) на минимальную высоту двух указателей. Мы должны сделать минимум, потому что вода переполнится, если мы выберем большее, что не имеет смысла. Теперь если высота левого меньше правого, то увеличиваем левое, стремясь к большей площади, иначе уменьшаем правое. Возвращает максимальную площадь после цикла while.

class Solution:
 def maxArea(self, height: List[int]) -> int:
  l, r, ans = 0, len(height) — 1, 0
 
  while l < r:
   ans = max(ans, 
             min(height[l], height[r]) * (r - l))
 
   if height[l] < height[r]:
    l += 1
   else:
    r -= 1
 
 return ans

Информация:

Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]