Математическое объяснение вопроса Leetcode: Контейнер с большим количеством воды ⇐ Python

[Anonymous]

Я работал над вопросом 11 по лит-коду среднего уровня. Контейнер с большим количеством воды. Помимо решения методом грубой силы с O(n^2), существует оптимальное решение со сложностью O(n) с использованием двух указателей с левой и правой стороны контейнера. Я немного не понимаю, почему этот метод «двух указателей» должен включать оптимальное решение. Кто-нибудь знает, как математически доказать правильность этого алгоритма? Это алгоритм, о котором я не знаю. Спасибо!
Исходный вопрос:

Вам дан целочисленный массив высотой длины n. Нарисовано n вертикальных линий, так что две конечные точки i-й линии — это (i, 0) и (i, height).
Найдите две линии, которые вместе с осью X образуют контейнер, например что в контейнере содержится больше всего воды. Возвращайте максимальное количество воды, которое может хранить контейнер. Обратите внимание, что вы не можете наклонять контейнер.

Грубое решение этого вопроса: (O(n^2)):

Код: Выделить всё

    def maxArea(self, height: List[int]) -> int:
length = len(height)
volumn = 0
#calculate all possible combinations, and compare one by one:
for position1 in range(0,length):
for position2 in range (position1 + 1, length):
if min(height[position1],height[position2])*(position2 - position1) >=volumn:
volumn = min(height[position1],height[position2])*(position2 - position1)
else:
volumn = volumn
return volumn

Оптимальный подход к решению. Я написал такой код (O(n)):

Код: Выделить всё

    def maxArea(self, height: List[int]) -> int:
pointerOne, pointerTwo = 0, len(height)-1
maxVolumn = 0
#Move left or right pointer one step for whichever is smaller
while pointerOne != pointerTwo:
if height[pointerOne] 

Подробнее здесь: [url]https://stackoverflow.com/questions/72064986/mathematical-explanation-of-leetcode-question-container-with-most-water[/url]