물이 가장 많은 용기

리트코드 문제: Container With Most Water

목적:

길이가 n인 정수 배열 높이가 주어집니다. i번째 선의 두 끝점이 (i, 0)과 (i, height[i])가 되도록 n개의 수직선이 그려집니다.

컨테이너가 가장 많은 물을 포함하도록 x축과 함께 컨테이너를 형성하는 두 개의 선을 찾습니다.

용기가 저장할 수 있는 최대 물의 양을 반환합니다.


패턴: 두 포인터 기술


접근하다:

왼쪽 및 오른쪽 포인터를 설정합니다. 왼쪽 포인터 = 0, 오른쪽 포인터 = array.length - 1.

왼쪽 포인터와 오른쪽 포인터 사이의 최대 영역을 추적하는 maxArea 변수를 만듭니다.

왼쪽 포인터와 오른쪽 포인터 사이의 너비를 추적하는 너비 변수를 만듭니다.

최대 면적을 계산하고 더 짧은 포인터를 가져와 너비를 곱합니다.

왼쪽 < 오른쪽 포인터인 경우 왼쪽 포인터를 늘리고 너비를 줄입니다.

왼쪽 > 오른쪽 포인터인 경우 오른쪽 포인터를 줄이고 너비를 줄입니다.

빅오 표기법:

시간 복잡도: O(n)
각 요소에 대해 n번 반복합니다.

공간 복잡도: O(1)
우리는 저장을 위해 추가 데이터 구조를 사용하지 않습니다.

암호:

class Solution {
    public int maxArea(int[] height) {

        int left = 0;
        int right = height.length - 1;
        int maxArea = Integer.MIN_VALUE;
        int width = height.length - 1; 

        while(left < right){
            int less = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, less * width);

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

            width--;
        }
        return maxArea;
    }
}