11. Container With Most Water

Container With Most Water - LeetCode

주어진 길이 n의 정수 배열 height가 있습니다. i번째 줄의 끝점은 (i, 0)와 (i, height[i])입니다. 가장 많은 물을 담을 수 있는 용기를 형성하는 두 개의 선을 찾아, 이 용기가 담을 수 있는 최대 물의 양을 반환합니다.

 

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1,1]
Output: 1

 

문제 요약:

주어진 선의 높이 배열을 사용하여, 두 개의 선을 선택하여 최대 물의 양을 찾는 문제입니다. 선을 오른쪽 또는 왼쪽으로 이동시켜서 물을 담을 수 있는 용기를 최대화합니다.

풀이과정 설명:

이 문제를 푸는 가장 효율적인 방법은 두 개의 포인터를 사용하는 것입니다. 처음에 가장 왼쪽과 오른쪽 인덱스를 가리키는 포인터인 left와 right를 초기화합니다. 그리고 현재 가리키는 선의 높이 중에서 더 작은 높이를 선택하여 이 높이를 h로 저장하고, 두 포인터 사이의 거리 w를 계산합니다. 현재의 물의 양은 h * w로 계산합니다.
이렇게 계산된 물의 양을 최대 물의 양과 비교하여 더 큰 값을 유지합니다. 그리고 높이가 더 낮은 쪽의 포인터를 안쪽으로 이동시켜 두 포인터 사이의 거리를 줄입니다. 이런 식으로 계속해서 포인터를 이동시키면서 최대 물의 양을 찾을 수 있습니다.

 

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        
        int leftP = 0;
        int rightP = height.length - 1;

        while(leftP < rightP){
            int _height = Math.min(height[leftP], height[rightP]);
            int _width = rightP - leftP;

            max = Math.max(max, _width * _height);
            
            if(height[leftP]  == _height){
                leftP++;
            }else{
                rightP--;
            }
        }
        return max;
    }
}