LeetCode 11 - Container With Most Water (Medium)

문제

LeetCode - 11번

풀이 과정

두 막대기를 기준으로 가장 많은 물을 담을 수 있는 방법을 찾는 문제입니다.

완전 탐색 으로 접근할 경우 O(N^2) 에 문제를 해결할 수 있지만 투 포인터 를 사용하면 O(N) 에 가능합니다.

두 막대가 다음과 같이 존재한다고 하겠습니다.

편의상 2, 1, 4 크기의 막대를 각각 다른 위치에 그렸지만
사실은 가장 왼쪽과 오른쪽 막대 중간의 어느 특정 위치 X 에 위치할 수 있는 막대의 3 종류를 나타낸 것입니다.

위와 같이 가장 왼쪽에 위치한 막대를 L 그 반대를 R 이라고 했을 때 어느 포인터를 옮겨야 최대 적재 컨테이너를 구할 수 있을까요?

만약 R 의 포인터를 왼쪽으로 옮길 경우 2, 1, 4 막대 모두 R 보다 작기 때문에 절대 더 큰 컨테이너를 구할 수 없습니다.
이는 각 컨테이너의 부피가 두 막대중 더 작은 막대기를 기준으로 높이가 결정되기 때문이죠.
대신에 L 을 오른쪽으로 옮길 경우 L 보다 큰 막대기가 존재할 경우 더 큰 컨테이너를 구할 가능성 이 존재합니다.

따라서 현재 두 포인터가 가르키는 막대 중 더 낮은 높이를 가지는 막대쪽의 포인터를 안쪽으로 옮겨주면서 탐색을 수행합니다.

코드

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let answer = 0;
  let left = 0,
    right = height.length - 1;

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

  return answer;
};