C++LeetCode 구현(11.물 을 가장 많이 담 는 용기)

[LeetCode]11.Container With 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 nis at least 2.

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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
이 가장 많은 물 을 담 는 용기 의 문제 와 저 문제.  Trapping Rain Water  비슷 하지만 약간 다르다.그 문 제 는 전체 가 빗물 을 수집 할 수 있 는 양 을 구 하 는 것 이다.이 문 제 는 가장 큰 수량 을 구 하 는 것 일 뿐이다.그리고 또 다른 것 은 그 문제 의 용기 가장자리 가 안에 포함 되 지 않 는 다 는 것 이다.이 문 제 는 계산 할 수 있다.비교 해 보면 이 문제 가 쉽다.여기 서 i 와 j 두 지침 이 각각 배열 의 좌우 양 끝 을 가리 키 는 것 을 정의 해 야 한다.그 다음 에 두 개의 포인터 가 중간 으로 검색 하고 한 번 이동 할 때마다 하나의 값 과 결 과 를 계산 하 는 것 이 비교적 크다.용기 의 수량 을 담 는 알고리즘 은 좌우 두 가장자리 에서 작은 것 을 찾 아 두 가장자리 의 거 리 를 곱 하 는 것 이다.코드 는 다음 과 같다.
C++해법 1:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            res = max(res, min(height[i], height[j]) * (j - i));
            height[i] < height[j] ? ++i : --j;
        }
        return res;
    }
};

자바 해법 1:

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) ++i;
            else --j;
        }
        return res;
    }
}

여기 서 주의해 야 할 것 은 자바 의 3 원 연산 자 A?B:C 는 반환 값 이 있어 야 하기 때문에 if.else.로 만 교체 할 수 있 습 니 다.자바 가 3 원 연산 자 에 대해 이렇게 엄격 한 제한 을 하 는 원인 이 무엇 인지 모 르 겠 습 니 다.
아래 의 이런 방법 은 위의 방법 에 대해 소폭 의 최적화 를 한 것 이다.같은 높이 에 대해 i 와 j 를 직접 이동 하면 된다.용량 을 계산 하지 않 는 다.코드 는 다음 과 같다.
C++해법 2:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
};

자바 해법 2:

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            res = Math.max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
}

C++구현 LeetCode(11.가장 많은 물 을 담 은 용기)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 가장 많은 물 을 담 은 용기 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!