Container With Most Water
Otrzymujesz listę height zawierającą nieujemne liczby całkowite. Linia i to pionowa ściana o wysokości height[i], stojąca na pozycji i. Dowolne dwie linie wraz z podłożem tworzą pojemnik, który mieści tyle wody, ile wynosi wysokość krótszej linii pomnożona przez odległość między tymi dwiema liniami. Pozostałe linie nie przeszkadzają. Zwróć maksymalną ilość wody, jaką może pomieścić jedna para linii.
Funkcja
- heightinteger-array
- wysokości linii na pozycjach 0, 1, 2 i tak dalej
- Zwracainteger
- najwięcej wody, jaką mogą pomieścić dwie linie
Ograniczenia
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- Wynik jest nie większy niż 108, więc mieści się w 32-bitowej liczbie całkowitej.
Przykłady
- Wejście
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- Wyjście
- 36
- Wyjaśnienie
- Linie na pozycjach 1 i 7, o wysokościach 7 i 6, są oddalone od siebie o 6 i mieszczą 6 × 6 = 36. Dwie najwyższe linie, te o wysokości 7 na pozycjach 1 i 5, mieszczą tylko 7 × 4 = 28.
- Wejście
- height = [4, 4]
- Wyjście
- 4
- Wyjaśnienie
- Dwie linie tworzą dokładnie jeden kontener: wysokość 4 i szerokość 1, więc mieści 4.
Pytanie dodatkowe
Tutaj pomijane są linie między tymi dwiema. Gdyby każda linia była pełnym słupkiem, ile wody zebrałoby się między nimi? Czy potrafisz obliczyć to również w O(n)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Zacznij od dwóch skrajnych linii: tworzą najszerszy pojemnik. Przesunięcie dowolnego końca do środka zmniejsza szerokość o jedną jednostkę. Która z tych dwóch linii mogłaby to zrekompensować?
Poziom wody wyznacza krótsza linia. Przesunięcie wyższej linii do środka zachowuje ten poziom, a zmniejsza szerokość, więc nigdy nie może pomóc. Szansę daje tylko zastąpienie krótszej linii.
Trzymaj wskaźnik na każdym końcu. Zmierz ilość wody między nimi i zachowaj najlepszy wynik, a następnie przesuń wskaźnik przy krótszej linii o jeden krok do środka. Zatrzymaj się, gdy wskaźniki się spotkają.
Rozwiązanie
Sprawdzenie wszystkich n²/2 par oznacza 5 × 10^7 iloczynów dla 10^4 linii. Ilość wody zależy tylko od krótszej linii w parze, więc gdy linia jest już krótszym bokiem najszerszego pojemnika, jaki może utworzyć, żaden węższy pojemnik, który jej używa, nie może pomieścić więcej wody. Dwa wskaźniki pozwalają przejść przez to w jednym przebiegu od obu końców.
Sprawdź każdą parę
Poprawne, ale nie kończy się na największych testach
Intuicja
Para i < j ma wartość min(height[i], height[j]) × (j - i): woda przelewa się przez niższą ściankę, a dno ma szerokość j - i. Sprawdź każdą parę i zachowaj największą wartość.
n linii daje n(n-1)/2 par: około 5 × 10^7 dla 10^4 linii, a za każdym razem, gdy n się podwaja, liczba par jest czterokrotnie większa.
Algorytm
- Ustaw
bestna 0. - Dla każdego
ii każdegojpo nim obliczmin(height[i], height[j]) × (j - i). - Zachowaj większą z wartości:
besti obliczoną wartość. - Zwróć
best.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return bestNajpierw najwyższe linie
Intuicja
Jeśli linia i jest krótszym bokiem pojemnika, jej partnerem może być dowolna linia co najmniej tak wysoka. Najlepszy taki pojemnik utworzy z nią linia położona najdalej spośród tych co najmniej tak wysokich.
Ułóż linie od najwyższej do najniższej. Gdy przychodzi kolej na linię i, każda już ułożona linia jest co najmniej tak wysoka, a najdalszy indeks wśród ułożonych linii to indeks skrajnie lewy lub prawy: lo albo hi. Zatem linia i może utworzyć pojemnik o polu co najwyżej height[i] × max(i - lo, hi - i), a najlepszy pojemnik jest uwzględniany, gdy przychodzi kolej na jego krótszą linię. Spośród dwóch równych linii ta ułożona jako druga widzi pierwszą jako partnera.
W pierwszym przykładzie linie o wysokości 7 na pozycjach 1 i 5 pojawiają się jako pierwsze i tworzą pojemnik o polu 28. Następnie linia o wysokości 6 na pozycji 7 widzi lo = 1 i tworzy pojemnik o polu 36. Sortowanie wymaga czasu O(n log n) i pamięci O(n).
Algorytm
- Posortuj indeksy według wysokości, od najwyższej.
- Ustaw
loihina pierwszy indeks w tej kolejności, abestna 0. - Dla każdego następnego indeksu
iobliczheight[i]pomnożone przez większą z wartościi - loihi - i, a następnie zachowaj najlepszą wartość. - Zaktualizuj
loihi, aby uwzględniałyi. - Zwróć
best.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return bestDwa wskaźniki z obu końców
Intuicja
Zacznij od najszerszego pojemnika, left = 0 i right = n-1, i załóż, że height[left] ≤ height[right]. Każdy inny pojemnik wykorzystujący linię left łączy ją z bliższą linią, więc jest węższy i nie wyższy niż height[left]. Żaden z nich nie mieści więcej wody niż zmierzona przez ciebie, więc linia left jest już rozpatrzona, a left przesuwa się o jeden krok w prawo. Przy równych wysokościach obie linie są już rozpatrzone, więc można przesunąć dowolną z nich.
Każdy krok eliminuje jedną linię, więc wskaźniki spotykają się po n-1 krokach. Najlepsza para nigdy nie zostaje pominięta: gdy usuwana jest pierwsza z jej dwóch linii, pojemnik zmierzony w tym momencie mieści co najmniej tyle samo.
W pierwszym przykładzie pozycje 0 i 7 mieszczą 21, a linia 3 zostaje usunięta. Pozycje 1 i 7 mieszczą 36, a linia 6 zostaje usunięta. Pozostałe pojemniki mieszczą 15, 28, 12, 10 i 2.
Algorytm
- Ustaw
left = 0,right = n-1ibest = 0. - Dopóki
left < right, obliczmin(height[left], height[right]) × (right - left)i zachowaj najlepszą wartość. - Jeśli
height[left] < height[right], przesuńlefto jeden krok w prawo. W przeciwnym razie przesuńrighto jeden krok w lewo. - Gdy wskaźniki się spotkają, zwróć
best.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Pułapki i przypadki brzegowe
- Przesuwanie wyższej linii. W pierwszym przykładzie, w którym wynik to 21 zamiast 36: 6 na pozycji 7 opuszcza układ, zanim w ogóle spotka 7 na pozycji 1.
- Używanie wyższej linii lub średniej z obu jako wysokości. Woda przelewa się przez niższą ściankę, więc wysokość to minimum.
- Mierzenie szerokości jako
j - i + 1. Linie na pozycjachiijsą oddalone od siebie oj - i, więc[4, 4]mieści 4, a nie 8. - Zakładanie, że odpowiedź wykorzystuje najwyższe linie lub skrajną parę. W pierwszym przykładzie dwie siódemki mieszczą 28, a skrajna para 21, podczas gdy odpowiedź to 36.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu „Container With Most Water”?
Rozwiązanie z użyciem dwóch wskaźników działa w czasie O(n) i wymaga O(1) dodatkowej pamięci, ponieważ w każdym kroku jeden wskaźnik przesuwa się o jedną pozycję do wewnątrz. Sprawdzenie każdej pary zajmuje O(n²), a posortowanie linii według wysokości — O(n log n).
Dlaczego przesunąć wskaźnik przy krótszej linii?
Poziom wody wyznacza krótsza linia. Każdy inny pojemnik zachowujący tę linię ma bliższego partnera, więc jest węższy i nie wyższy. Żaden z nich nie może być lepszy od zmierzonego przez ciebie pojemnika, więc możesz pominąć krótszą linię, nie tracąc poprawnej odpowiedzi.
Czy „Container With Most Water” jest problemem zachłannym?
Tak. Na każdym kroku podejmujemy lokalną decyzję, której już nie cofamy: opuszczamy krótszą linię. Ta decyzja jest bezpieczna, ponieważ każdy wykluczony przez nią pojemnik nie jest lepszy od już zmierzonego, dlatego to zadanie zalicza się zarówno do algorytmów zachłannych, jak i do metody dwóch wskaźników.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def maxArea(height):
# Wpisz kod tutajTest #1
Test #2
Argument
height = [3, 7, 2, 5, 4, 7, 3, 6]
Oczekiwany wynik
36