>

작업 leetcode

에서 가져옵니다.

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.

내 첫 번째 해결책 :

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = height => {
  let max = 0;
  height.forEach((hL, i) => {
    height.slice(i + 1).forEach((hR, j) => {
      max = Math.max(max, Math.min(hL, hR) * (1 + j));
    });
  });
  return max;
};

두 번째 해결책 :

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea2 = height => {
  let l = max = 0;
  let r = height.length - 1;
  while (l < r) {
    const area = Math.min(height[l], height[r]) * (r - l);
    if (height[l] > height[r]) {
      r--;      
    } else {
      l++;
    }
    max = Math.max(max, area);
  }
  return max;
};

수학적으로 해결하고 더 빠르게 만들 수 있습니까?


  • 답변 # 1

    와이즈 비즈

    두 번째 솔루션보다 빠르지 않은 \ $O (n) \ $이며 입력을 한 번에 전달합니다. 모든 요소를 ​​검사하지 않고 정답을 찾을 수 없다는 것을 쉽게 알 수 있습니다. 예를 들어 두 값을 검사하지 않으면 임의로 높은 값을 선택하여 최대 면적을 생성 할 수 있습니다.

    두 번째 해결책에 대한 스타일 의견이 있습니다 :

    변수 이름

    Is it possible to solve it mathematically and make it faster?

    를 싫어합니다  일부 글꼴에서는 l 와 혼동 될 수 있기 때문에  또는 | .

    1 의 이름을 바꾸겠습니다.   l 로  그리고 left   r 로  자연스러운 선명도. 여전히 간단합니다.

    right 와의 대칭 나는 while (l < r) 를 다시 쓸 것입니다  루프 바디에서 if 생각하면 논리를 이해하는 데 도움이됩니다.

    if (height[l] < height[r])

  • 이전 python - "미니언 게임"도전
  • 다음 c# - 클라이언트 응용 프로그램의 DTO를 서비스 프록시의 DataContract에 매핑