물이 가장 많은 용기
문제 요구 사항
길이 n 의 정수 높이의 배열이 주어집니다. n 개의 수직선이 있고, i 번째 선의 두 끝점은 와 입니다.
X축과 함께 가장 많은 물을 담을 수 있는 용기를 형성하는 두 개의 선을 찾습니다.
컨테이너에 저장할 수 있는 최대 물의 양을 반환합니다.
참고: 컨테이너를 기울일 수 없습니다.
예 1:
입력합니다:[1,8,6,2,5,4,8,3,7]
출력: 49
설명: 다이어그램의 수직선은 입력 배열을 나타냅니다.[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49。
예 2:
입력: 높이= [1,1]
출력: 1
알고리즘 아이디어
루프를 반복하여 최대 값을 얻습니다.
알고리즘 코드
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxValue = 0;
let temp = 0;
for(let i=0;i<height.length;i++){
for(let j =height.length-1;j>i;j--){
if(height[i]*(height.length-i-1)<maxValue){
break;
}
if(height[i]>height[j]){
temp= height[j]*(j-i);
}else{
temp= height[i]*(j-i);
}
if(maxValue<temp){
maxValue=temp;
}
}
}
return maxValue;
};
결과
letCode공식 솔루션
문제 해결을 위한 아이디어
방법 1: 더블 포인터 설명
분석
이중 포인터 알고리즘의 프로세스는 제목의 예제부터 단계별로 설명합니다. 알고리즘의 정확성에 대한 증명은 나중에 설명하겠습니다.
제목의 예는 다음과 같습니다:
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ ^ 처음에 왼쪽과 오른쪽 포인터는 배열의 왼쪽과 오른쪽 끝을 가리키며, 이들이 담을 수 있는 물의 양은 min∗8=8\min(1, 7) * 8 = 8min(1,7)∗8=8입니다.
이 시점에서 포인터를 이동해야 합니다. 어느 포인터를 이동해야 할까요? 직감적으로 더 작은 숫자에 해당하는 포인터를 이동해야 합니다. 왜냐하면 포인터가 보유한 물의 양이
두 포인터가 가리키는 숫자 중 더 작은 숫자 ∗ 포인터 사이의 거리 두 포인터가 가리키는 숫자 중 더 작은 숫자 * 포인터 사이의 거리 두 포인터가 가리키는 숫자 중 더 작은 숫자 ∗ 포인터 사이의 거리 결정됩니다. 더 큰 숫자를 가진 포인터를 이동하면 전자의 "두 포인터가 가리키는 숫자 중 더 작은 숫자"는 증가하지 않고 후자의 "포인터 사이의 거리"가 감소하여이 곱이 감소합니다. 따라서 더 큰 숫자로 포인터를 이동하는 것은 의미가 없습니다. 따라서 숫자가 작은 포인터로 포인터를 이동하세요.
두 개의 포인터를 동시에 이동하는 것이 가능한지 궁금해하는 독자도 있을 것입니다. 걱정하지 마세요. 항상 작은 포인터를 이동한다는 아이디어가 옳다고 가정하고 프로세스를 진행한 후 증명해 보겠습니다.
따라서 왼쪽 포인터를 오른쪽으로 이동합니다:
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ ^ 이 지점에서 수용할 수 있는 물의 양은 min∗7=49\min(8, 7) * 7 = 49min(8,7)∗7=49입니다. 오른쪽 포인터가 작은 수에 해당하므로 오른쪽 포인터를 이동합니다:
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ ^ 이 지점에서 수용할 수 있는 물의 양은 min∗6=18\min(8, 3) ∗ 6 = 18min(8,3)∗6=18입니다. 오른쪽 포인터가 작은 수에 해당하므로 오른쪽 포인터를 이동합니다:
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ ^ 이 지점에서 담을 수 있는 물의 양은 min∗5=40\min(8, 8) ∗ 5 = 40min(8,8)∗5 = 40입니다. 두 포인터는 같은 수에 해당하며 왼쪽 포인터와 같이 어느 한 포인터로 이동할 수 있습니다:
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ ^ 이 지점에서 담을 수 있는 물의 양은 min∗4=24\min(6, 8) * 4 = 24min(6,8)∗4=24입니다. 왼쪽 포인터가 작은 수에 대응하므로 왼쪽 포인터를 움직이면 이 지점 이후에는 항상 왼쪽 포인터가 작은 수에 대응하므로, 왼쪽 포인터를 계속 움직이게 됩니다. 두 포인터가 일치할 때까지 왼쪽 포인터를 계속 움직입니다. 이 기간 동안 수용할 수 있는 물의 양은 min∗3 = 6\min(2, 8) * 3 = 6min(2,8)∗3 = 6, min∗2 = 10\min(5, 8) * 2 = 10min(5,8)∗2 = 10, min∗1 = 4\min(4,8) * 1 = 4min(4,8)∗1=4.
포인터를 이동하는 과정에서 수용할 수 있는 최대 수는 494949로 계산되며, 이것이 최종 답입니다.
작성자: 파워 버클 공식 질문 설명 링크: 출처: 파워 버클 판권 소유. 상업적 복제의 경우 저작자에게 문의하여 승인을 받으시고, 비상업적 복제의 경우 출처를 명시하시기 바랍니다.
솔루션 코드
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxValue = 0;
let l = 0;
let r = height.length-1;
while(l<r){
let area = Math.min(height[l], height[r]) * (r - l);
maxValue = Math.max(maxValue, area);
if(height[l]<=height[r]){
l++;
}else{
r--;
}
}
return maxValue;
};
