[leetcode] 11. 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

 

풀이

구간 [$l,r$]에 대해서 $f(l,r) = (r-l) \times \min(height[l], height[j])$를 정의한다.

그렇다면 구하고자 하는 것은 $\max(f(l,r))$이 된다.

 

지금은 총 $O(n^2)$의 순서쌍을 탐색해야 하지만, 약간의 성질을 이용하면 모든 순서쌍을 검사하지 않아도 된다.

 

1) $height[l]<height[r]$ 이라면, 임의의 $x \in [l,r]$에 대해서 $f(l,r) \geq f(l,x)$

2) $height[l]>height[r]$ 이라면, 임의의 $x \in [l,r]$에 대해서 $f(l,r) \geq f(x,r)$

 

1번과 2번 성질의 증명과정은 같으므로 예시로 1번 성질만 증명하겠다.

$$f(l,r)=(r-l)\times height[l]\geq(x-l)\times height[l]\geq(x-l)\times\min(height[l], height[x])=f(l,x)$$

 

따라서 현재 $[l,r]$을 탐색하고 있을 때, 더 나은 답은 답을 얻기 위해선, 둘 중에 더 낮은 쪽을 움직이는 것으로 정답이 될 가능성이 있는 경우를 다 둘러볼 수 있다는 말이 된다.

 

Time Complexity : $O(n)$

 

코드

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0, r=height.size()-1, ans=0;
        while(l<r)
        {
            ans = max(ans, (r-l)*min(height[r],height[l]));
            if(height[l]<height[r])l++;
            else r--;
        }
        return ans;
    }
};