물이 가장 많은 용기: 해답 면적 알고리즘

오늘의 알고리즘은 Container with the Most Water:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2.

이것은 Leetcode의 문제입니다. 그 어휘는 매우 복잡하고 틀림없이 예시가 필요할 것입니다.수조 [1,8,6,2,5,4,8,3,7] 를 획득했다고 가정하십시오.이 숫자들을 막대 그림에 놓으면 다음과 같은 결과를 얻을 수 있다.

문제가 "물이 가장 많은 용기"를 요구할 때, 이것은 당신이 이 도표의 임의의 두 수직 줄 사이에 수평선을 그으면, 어느 것이 가장 면적이 큰지 의미합니다.다시 말하면 이 술집에 장방형의 물용기가 있다면 어느 용기가 가장 큽니까?다음 그림에서는 두 개의 빨간색 막대로 고정된 컨테이너가 가장 큽니다.

본고에서 나는 이 문제를 어떻게 해결하는지 상세하게 소개한 다음에 자바스크립트를 사용하여 그것을 해결할 것이다.

문제를 해결하다

이 문제를 해결하는 방법 중 하나는 주어진 그룹의 매 쌍의 높이를 검사하여 그들 사이의 면적을 확정한 다음에 면적이 가장 큰 것으로 되돌아오는 것이다.이런'폭력'해결 방안은 우리에게 정확한 답을 줄 수 있지만, 결코 최적화되지 않았다.따라서 우리는 몇 개의 선과 그 사이의 구역만 검사하는 방법을 찾아야 한다.
설명에 따르면 물을 담는 용기는 반드시 직사각형이어야 한다. 즉, 한쪽에 사선이 있어서는 안 된다는 것이다.이것은 최대 용기의 높이가 반드시 가장 높은 선에 의해 결정되는 것이 아니라는 것을 의미한다.
첫 번째 예를 다시 한 번 봅시다. 물이 가장 많은 용기의 높이는 8개 단위 길이의 선이 아니라 7개 단위 길이의 선에 의해 결정됩니다.

이것은 우리가 이 문제를 어떻게 해결하는지에 단서를 제공했다.우리는 항상 두 줄을 동시에 검사하려고 한다. 우리는 그 중의 하나를'왼쪽'행, 다른 하나를'오른쪽'행이라고 할 수 있다.우리는 비교적 작은 하나, 왼쪽이나 오른쪽을 찾은 후에 이 두 선 사이의 면적을 찾을 수 있다.우리는 두 개의 바늘로 이 두 선을 추적할 것이다. left, 그것은 왼쪽의 선을 가리키고, right, 그것은 오른쪽의 선을 가리킨다.
첫 번째 줄left과 마지막 줄right부터 시작해서 left보다 작으면 계속 검사하는 순환을 만들 것입니다.우리는 이 두 선 사이의 구역을 찾을 것이다. 그리고 우리는 왼쪽 바늘을 중심으로 옮길지, 아니면 오른쪽 바늘을 중심으로 옮길지 결정할 수 있다.만약 왼쪽 선이 오른쪽 선보다 작다면 진열에 더 높은 선이 있을 뿐만 아니라 더 큰 면적이 생길 수 있다.따라서 우리는 왼쪽 바늘을 늘리기를 바란다.만약 오른쪽의 선이 왼쪽의 선보다 작다면 수조의 앞에 선이 더 높고 더 큰 면적이 생길 수 있다.따라서 우리는 오른쪽 바늘을 줄이거나 1을 줄이기를 바란다.

구해 알고리즘

우선, 우리는 몇 개의 변수를 초기화할 것이다.right 최대 면적을 저장하고 마지막으로 돌아갑니다.max는 인덱스 0에서 시작하는 왼쪽 포인터입니다.left는 오른쪽 바늘로 입력 수조의 마지막 원소right부터 시작한다.

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

  //...
  return max;
}

현재, 우리는while 순환을 만들 것입니다. height 보다 작으면 계속 실행됩니다.우리는 left 변수가 가리키는 선right과 left 변수가 가리키는 선height[left]에 접근할 수 있다.어느 것이 더 작은지 알고 싶기 때문에while 순환에서 right라는 변수를 만들 것입니다.height[right] 방법은 smallerLine 방법을 사용하고 이 방법은 두 정수 중 비교적 작은 하나를 되돌려줍니다.우리는 왼쪽과 오른쪽을 지나갈 것이다.

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

  while (left < right) {
    let smallerLine = Math.min(height[left], height[right]);
    //...
  }
  return max;
}

현재, 우리는 두 선 사이의 면적이 우리가 발견한 현재의 최대 면적보다 큰지 보고 싶다.이를 검사하기 위해 우리는 smallerLine, 전류Math.min(), 그리고Math.max()를 사용할 수 있다.직사각형의 면적은 높이에 너비를 곱하여 계산한다.높이는 max 에서 결정되며 폭은 smallerLine * (right - left) 과 smallerLine 포인터 사이의 거리입니다.우리는 right 를 비교적 큰 값으로 설정할 것이다.

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

  while (left < right) {
    let smallerLine = Math.min(height[left], height[right]);
    max = Math.max(max, smallerLine * (right - left));
    //...
  }
  return max;
}

만약 왼쪽 줄이 오른쪽 줄보다 작다면, 우리는 left 변수를 증가해야 한다.그렇지 않으면, 우리는 변수를 줄일 것이다.어느 때,left는right보다 작지 않으며,while 순환이 실행됩니다.이런 상황이 발생하면 함수는 찾은 최대 면적을 포함하여 max 되돌아옵니다.

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

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

--
만약 당신에게 어떤 문제나 기타 이 문제를 해결하는 방법이 있다면 저에게 알려주세요!