LeetCode 11 - Container With Most Water

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

 

가장 많은 물을 가두기 위해 어느 두 점을 선택해야 하는가.

너비라는 것이 가로 x 세로이다. 일단 가로를 가장 길게 설정해 둔 다음 가로를 좁혀가며 최댓값을 변경하면 될 것 같다.

이때 가로를 어떻게 좁히느냐가 문제인데 작은 것을 기준으로 세로가 정해지기 때문에 세로값이 작은 것을 변경시키는 방향으로 가는 것이 맞다.

class Solution {
    public int maxArea(int[] height) {
        int max = Integer.MIN_VALUE;

        int left = 0;
        int right = height.length - 1;

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

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

        return max;
    }
}