[LeetCode] Container With Most Water

문제

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

 

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

 

Example:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

 

Approach

단순히 Brute force로 O(n^2)만에 풀면 되지만

당연히 더 좋은 방법이 있다

 

Optimization

넓이는 기둥간 거리를 가로로, 두 기둥 중 짧은 기둥의 높이를 세로로 한다.

즉 거리가 넓으면 넓을 수록 좋고, 이 거리를 줄이게 된다면 그 만큼 세로가 더 높아져야 넓이가 늘어나게 된다.

그러므로 시작은 일단 끝과 끝에서 시작하되,

두 기둥중 짧은 기둥의 높이보다 길이가 같거나 긴 기둥을 만날 때 까지 양쪽의 기둥 포인터를 안쪽으로 좁힌다. (증명)

이러면 O(n)만에 풀이가 가능하다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_ContainerWithMostWater.cpp

chi3236/algorithm