[Leetcode] 11container-with-most-water (Java, Javascript)

문제

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

문제설명

n개의 양수로 이루어진 수직 그래프가 주어진다. 두 개의 수직선을 이용하여 컨테이너를 만든다고 가정할 때 가장 물을 많이 담을 수 있는 넓이를 구하는 문제이다. (단, 컨테이너를 기울 일 수 없다. => 두 개의 수직선 중 높이가 낮은 선을 높이로 계산해야한다.)

해결방법

최대 넓이를 구해야하는 문제이므로 바깥에서 안쪽으로 범위를 좁혀가며 최대 넓이를 구한다.

가장 왼쪽에 있는 선과(첫번째선) 가장 오른쪽에 있는 선(마지막 선)을 선택하고
왼쪽, 오른쪽 선들을 각각 오른쪽, 왼쪽으로 한칸씩 이동시킬 때 어차피 길이가 짧은선은 (노란색 박스) 길이가 긴 선보다 (파란색 박스) 넓이가 작을 수 밖에 없다.
따라서 왼쪽, 오른쪽 선의 높이 중 더 낮은 높이의 선의 위치를 선택하여 하나씩 이동시킨다.
(왼쪽 선인 경우 오른쪽으로 한칸 이동, 오른쪽 선인 경우 왼쪽으로 한칸 이동)
왼쪽에 위치하는 선이 오른쪽에 위치하는 선보다 커지기 전까지 반복하여 최대 넓이를 구한다.

코드

Javascript

var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let max = 0;

  while (left < right) {
    max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return max;
};

Java

public int maxArea(int[] height) {
	int left = 0;
	int right = height.length - 1;
	int max = 0;
	while(left < right) {
		max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
		if(height[left] < height[right]) {
			left ++;
		}else {
			right --;
		}
	}
	
	return max;
}