물이 가장 많은 LeetCode 컨테이너
16703 단어 cppleetcodejavascriptgo
문제 설명
주어진 N개의 음이 아닌 정수 a1, a2, ..., an,
여기서 각각은 좌표(i, ai)의 점을 나타냅니다.
선의 두 끝점이 되도록 N개의 수직선이 그려집니다.
i는 (i, ai) 및 (i, 0)에 있습니다.
x축과 함께 컨테이너를 형성하는 두 개의 선을 찾습니다.
용기에 물이 가장 많이 담기도록 합니다.
문제 진술 출처: https://leetcode.com/problems/container-with-most-water
예 1:
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
예 2:
Input: height = [1, 1]
Output: 1
예 3:
Input: height = [4, 3, 2, 1, 4]
Output: 16
예 4:
Input: height = [1, 2, 1]
Output: 2
제약:
- N == height.length
- 2 <= N <= 10^5
- 0 <= height[i] <= 10^4
설명
무차별 대입
무차별 접근 방식은 가능한 모든 선 쌍의 영역을 고려하는 것입니다.
그리고 그들 중 최대를 찾으십시오.
접근 방식의 C++ 스니펫은 다음과 같습니다.
public class Solution {
public int maxArea(int[] height) {
int ans = 0;
for (int i = 0; i < height.length; i++)
for (int j = i + 1; j < height.length; j++)
ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
return ans;
}
}
접근 방식의 시간 복잡도는 O(N^2)입니다.
두 개의 중첩 for 루프와 배열의 모든 하위 집합을 고려합니다.
두 개의 포인터
2점 포인터를 사용하면 시간 복잡도를 줄일 수 있습니다.
라인이 멀수록 더 많은 면적을 얻을 수 있다는 것을 알고 있습니다.
그러나 선 사이에 형성되는 영역은 제한됩니다.
더 짧은 선의 높이만큼.
연산
- set left and right pointer to 0 and last index of array height
- set ans = 0. Variable ans holds the max area of our solution
// Iterate array from both ends and
- Loop while left < right
- get the area between to indices
- area = min(height[left], height[right])*(right - left)
- get the maximum of ans and area and update ans
- ans = max(ans, area)
- increment left or right based on which of the index value is minimum.
- if height[left] < height[right]
- increment left++
- else
- increment right++
- return ans
C++ 솔루션
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ans = 0;
while(left < right){
ans = max(ans, min(height[left], height[right])*(right-left));
if(height[left] < height[right]){
left += 1;
} else {
right -= 1;
}
}
return ans;
}
};
골랑 솔루션
func maxArea(height []int) int {
left, right := 0, len(height) - 1
area := 0
for left < right {
area = max(area, min(height[left], height[right])*(right - left))
if height[left] < height[right] {
left++
} else {
right--
}
}
return int(area)
}
func max(a, b int) int{
if a > b {
return a
}
return b
}
func min(a, b int) int{
if a < b {
return a
}
return b
}
자바스크립트 솔루션
var maxArea = function(height) {
if (height.length < 2){
return 0;
}
let left = 0;
let right = height.length - 1;
let ans = 0;
while (left < right) {
ans = Math.max(ans, Math.min(height[left], height[right]) * (right - left) );
if (height[left] < height[right]){
left += 1;
} else {
right -= 1;
}
}
return ans;
};
솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left = 0
right = height.size() - 1
= 9
ans = 0
Step 1: left < right
0 < 8
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(0, min(1, 7)*(8-0))
= max(0, 1*8)
= max(0, 8)
= 8
height[left] < height[right]
1 < 7
true
left++ = 1
Step 2: left < right
1 < 8
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(8, min(8, 7)*(8-1))
= max(8, 7*7)
= max(8, 49)
= 49
height[left] < height[right]
8 < 7
false
right-- = 7
Step 3: left < right
1 < 7
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 3)*(7-1))
= max(49, 3*6)
= max(49, 18)
= 49
height[left] < height[right]
8 < 3
false
right-- = 6
Step 4: left < right
1 < 6
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 8)*(6-1))
= max(49, 8*5)
= max(49, 40)
= 49
height[left] < height[right]
8 < 8
false
right-- = 5
Step 5: left < right
1 < 5
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 4)*(5-1))
= max(49, 4*4)
= max(49, 16)
= 49
height[left] < height[right]
8 < 4
false
right-- = 4
Step 6: left < right
1 < 4
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 5)*(4-1))
= max(49, 5*3)
= max(49, 15)
= 49
height[left] < height[right]
8 < 5
false
right-- = 3
Step 7: left < right
1 < 3
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 2)*(3-1))
= max(49, 2*2)
= max(49, 4)
= 49
height[left] < height[right]
8 < 2
false
right-- = 2
Step 8: left < right
1 < 2
true
ans = max(ans, min(height[left], height[right])*(right-left));
= max(49, min(8, 6)*(2-1))
= max(49, 6*1)
= max(49, 6)
= 49
height[left] < height[right]
8 < 6
false
right-- = 1
Step 9: left < right
1 < 1
false
return ans as 49
Reference
이 문제에 관하여(물이 가장 많은 LeetCode 컨테이너), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-container-with-most-water-1mcg텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)