.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Plain Text
복사
Example 2:
Input: height = [1,1]
Output: 1
Plain Text
복사
Constraints:
•
n == height.length
•
2 <= n <= 105
•
0 <= height[i] <= 104
My solution
길이가 n인 정수 배열 높이가 지정된다.
i번째 선의 두 끝점이 (i, 0)과 (i, height[i])이 되도록 n개의 수직선이 그려져 있다.
x축과 함께 container를 형성하는 두 선을 찾아라. 그것은 가장 많은 물을 포함해야 한다.
용기에 저장할 수 있는 물의 최대 양을 반환한다.
용기는 기울일 수 없다.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Plain Text
복사
이 예시에서는 2번째인 8과 마지막 7이 만드는 컨테이너가 가장 많은 물을 가질 수 있다.
채울 수 있는 공간이 7개이고 높이가 7이기 때문에 총 49가 되었다.
두개의 수직선을 가리키면서 최대양을 매번 검사해주면서 업데이트해줘야된다는 생각을 했다.
인덱스만 있어도 x축의 길이는 알수 있지만 높이도 알아야 매번 최대양을 계산해줄 수 있으니 높이를 구하기 위해서 lt, rt 포인터를 height배열에 인덱스로 줘서 해당 값에 접근해 가져온다.
더 낮은 높이의 수직선만큼만 물을 채울 수 있다.
대략 이렇게 짜볼 수 있다.
let lt = 0;
let rt = len -1;
while(lt < rt) {
const 뮬의양 = (height[lt] > height[rt] ? height[rt] : height[lt]) * (rt - lt);
max = Math.max(max, 물의 양)
if(height[left] < height[right]){
// 즉, height가 작은 쪽의 포인터를 한칸씩 이동시키는 것이다.
// 이동 후에 물의 양이 더 늘어날 수 있기 때문이다.
left++;
else {
right--;
}
}
JavaScript
복사
Code
/**
* @param {number[]} height
* @return {number}
*/
const maxArea = function (height) {
let left = 0;
let right = height.length - 1;
let max = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
max = Math.max(max, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
};
describe('maxArea', () => {
it('TC1', () => {
expect(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])).toStrictEqual(49);
});
it('TC2', () => {
expect(maxArea([1, 1])).toStrictEqual(1);
});
});
JavaScript
복사
