(LeetCode) 11. Container With Most Water

The link : leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

문제는 다음과 같다. 

1. 배열의 값이 순차적으로 주어진다. 

2. 물을 채울 컨테이너의 최대값을 구한다. 

3. 즉, x의 길이가 최대이고 y의 길이가 최대인 영역의 넓이를 구하면 된다.

---

문제 풀이는 다음과 같다. 

1. 투 포인터 접근으로 푼다. 이 외에 스택으로도 풀 수 있다. 

2. 왼쪽지점은 배열의 첫 번째 시작점, 즉, 0으로 잡는다. 오른쪽 지점은 배열의 마지막 지점, 즉, 길이-1로 잡는다. 

3. 컨테이너 넓이의 높이는 왼쪽과 오른쪽 중 적은 값으로 정한다.

4. 기존의 정답과 컨테이너의 (오른쪽 - 왼쪽) * 3번의 높이 중, 최대값을 정답으로 선정한다.

5. 만약 왼쪽값이 오른쪽값보다 크다면 오른쪽 값을 한 칸 -1 해준다. 

6. 반대로 왼쪽값보다 오른쪽값이 크다면 왼쪽 값을 한 칸 +1 해준다. 

7. 이 과정을 서로가 겹치지 않을때까지 반복하면 가장 큰 영역의 값을 구할 수 있다. 

+ 당연하지만 Brutce Force로 2중 for문을 사용하면 시간초과가 나온다.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ans = 0;
        while(left<right){
            int temp = min(height[left],height[right]); // 둘중 작은 높이를 기준으로 삼기
            ans = max(ans, (right-left)*temp);
            if(height[left]<height[right]) left++;
            else right--;
        }
        return ans;
    }
};