/leetcode 11/ Container With Most Water

n 개의 0이 아닌 정수 a(1), a(2), ... , a(n)는 각각 수직으로 그려진 막대의 높이를 의미한다.

x축과 함께 두 개의 막대로 만들 수 있는 컨테이너 중에서 가장 많은 물을 담을 수 있는 경우를 찾아서 그 때의 넓이를 반환한다.

 

가장 쉽게 생각해볼 수 있는 방법은 모든 경우의 넓이를 구해서, 최대 넓이를 구하는 방식이다.

이러한 brute force 방식은 time complexity가 O(n^2)이므로 효율적일 수 없다.

( leetcode runtime에서 실행시간 1240ms, 메모리 사용량은 9.8MB가 사용되었다.)

 

이에 따라서 Solution에 제시된 Two Pointer Approach를 적용해본다.

 

Two Pointer Approach는 컨테이너에 담는 물은 두 개의 막대 중에서 낮은 막대에 의해 결정된다는 사실에 착안한다.

따라서 현재의 넓이를 구한 다음에, 두 막대 중 낮은 막대는 

다음에 더 높은 막대가 있을 가능성을 믿고

다음 막대로 교체한다는 것이 이 알고리즘의 원리이다.

 

time complexity는 O(n)이 될 것이다.

( leetcode runtime에서 실행시간은 16ms, 메모리 사용량은 9.8MB가 사용되었다.)