Container With Most Water

Każdy pojemnik to para pozycji i < j. Woda podnosi się, aż przeleje się przez niższą ściankę, a dno między ściankami ma szerokość j - i, więc para mieści min(height[i], height[j]) × (j - i). Sprawdź każdą parę, zachowaj największą wartość i z definicji otrzymasz odpowiedź.

Problemem jest liczba par. n linii daje n(n-1)/2 par: około 5 × 10^7 dla 10^4 linii, a za każdym razem, gdy lista się podwaja, ich liczba wzrasta czterokrotnie. Język kompilowany wykona to w ułamku sekundy, ale Python, Ruby lub R potrzebują wielu sekund, a liczba par rośnie zbyt szybko dla każdego języka, gdy n osiąga 10^5.

Spójrz na pojemnik od strony jego krótszego boku. Jeśli bok i jest krótszy, pojemnik mieści height[i] razy odległość, a jego drugim bokiem może być dowolny bok o co najmniej takiej samej wysokości. Najlepszy pojemnik, w którym i jest krótszym bokiem, tworzy więc z nim najdalszy bok o co najmniej takiej wysokości.

Aby szybko znaleźć takie drugie boki, ustaw boki od najwyższego do najniższego. Gdy przychodzi kolej na bok i, każdy bok ustawiony przed nim ma co najmniej taką samą wysokość, a najdalszy z nich znajduje się albo na skrajnym lewym, albo na skrajnym prawym spośród ustawionych indeksów. Śledź te dwa indeksy: lo i hi. Bok i może wtedy pomieścić najwyżej height[i] × max(i - lo, hi - i). Odpowiedzią jest największa z tych wartości, ponieważ najlepszy pojemnik zostaje uwzględniony, gdy przychodzi kolej na jego krótszy bok.

W pierwszym przykładzie dwa boki o wysokości 7 na pozycjach 1 i 5 pojawiają się jako pierwsze i mieszczą 28. Następnie pojawia się bok o wysokości 6 na pozycji 7, z lo = 1 i hi = 5; mieści on 6 × 6 = 36. Żaden niższy bok nie daje lepszego wyniku. Boki o równej wysokości mogą pojawiać się w dowolnej kolejności: ten z dwóch równych boków, który pojawi się jako drugi, zobaczy pierwszy jako możliwy drugi bok.

Sortowanie zajmuje O(n log n), a przejście O(n), co jest wystarczająco szybkie. Nadal potrzeba O(n) pamięci na kolejność, a następne podejście pozwala zrezygnować zarówno z sortowania, jak i z tej pamięci.

Zacznij od najszerszego pojemnika: left = 0 i right = n-1, a następnie zmierz jego pojemność. Teraz można odsunąć jedną z dwóch linii, a wybór jest oczywisty: odsuń krótszą. Załóżmy, że height[left] ≤ height[right]. Każdy inny pojemnik wykorzystujący linię left łączy ją z linią położoną bliżej niż right, więc jest węższy, a jego wysokość nadal wynosi co najwyżej height[left]. Żaden z nich nie pomieści więcej wody niż zmierzony pojemnik, więc linia left jest już rozpatrzona, a left przesuwa się o jeden krok w prawo. Przesunięcie zamiast niej wyższej linii zachowałoby ten sam limit wysokości i zmniejszyłoby szerokość, więc wynik może być tylko gorszy. Gdy wysokości obu linii są równe, obie są już rozpatrzone, więc można przesunąć dowolną z nich.

W każdym kroku jedna linia zostaje na stałe wyeliminowana, więc po n-1 krokach wskaźniki się spotykają. Najlepsza para nigdy nie zostaje pominięta: gdy jedna z jej dwóch linii zostaje odsunięta po raz pierwszy, zmierzony w tym momencie pojemnik mieści co najmniej tyle samo wody.

Dla [3, 7, 2, 5, 4, 7, 3, 6] pozycje 0 i 7 mieszczą 3 × 7 = 21. Linia o wysokości 3 jest krótsza, więc left przesuwa się na pozycję 1. Pozycje 1 i 7 mieszczą 6 × 6 = 36, a teraz krótsza jest linia o wysokości 6, więc right przesuwa się na pozycję 6. Kolejne pojemniki mieszczą 15, 28, 12, 10 i 2, więc wynik pozostaje równy 36.