(Array, Medium) Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/

일단 미디엄 문제이기 때문에 O(n^2)는 버리는 것으로 생각하고 ..

투포인터를 쓰면 될 것 같다.

while로 순회마다 두 포인터 중 하나는 감소하거나 증가할테니 O(N)
max 변수를 설정해두고 Math.max로 갈아치워준 뒤 루프끝나면 답이 있을 듯

max값을 계속 갈아치울 current sum을 구하는 공식은 left와 right사이의 공간에다가 둘 중 낮은 값을 곱하면 된다.

그럼 언제 left 혹은 right를 이동시킬지는 어떻게 결정할 수 있을까?
기본적으로 가장 많은 물을 담고 싶으면 넓을수록 좋고, 높을수록 좋다.

넓을수록 좋다 - 투포인터로 left, right 왼쪽 끝과 오른쪽 끝부터 시작해서 좁혀간다.
높을수록 좋다 - left와 right중 작은 것을 이동시킨다.

따라서 height[left] < height[right] 라면 left ++,
그렇지 않다면 right-- 해주면서 더 큰 테두리를 찾아나가면 된다.

class Solution {
    public int maxArea(int[] height) {
        
        int left = 0;
        int right = height.length - 1;

        int max = 0;
        while (left < right) {
            int gap = right - left;
            int sum = Math.min(height[left], height[right]) * gap;

            max = Math.max(sum, max);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max;
    }
}