LeetCode - 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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

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.

Example 2:

Input: height = [1,1]
Output: 1

제약사항

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

Solution 1

[전략] Brute Force

• 모든 i, j 라인에 대해 높이가 더 낮은 라인을 기준으로 product를 구함

public int maxArea2(int[] height) {

        int inputLength=height.length;
        int maxProduct=0;

        for (int i = 0; i < inputLength; i++) {

            for (int j = i + 1; j < inputLength; j++) {
                int h = height[i] > height[j] ? height[j] : height[i];
                int subProduct = h * (j - i);
                if (subProduct > maxProduct) {
                    maxProduct = subProduct;
                }
            }
        }
        return maxProduct;
    }

Solution 2

[전략]
양 끝에 포인트를 각각 두고 포인트를 하나씩 옮기면서 최대 product를 구한다.

• 포인트를 옮기는 기준은 두 포인트 중 짧은 포인트를 옮긴다.
• 긴 길이의 점을 옮겨 더 긴 길이를 만나더라도 h의 기준은 짧은 길이이고 너비만 줄어들 뿐이므로 불필요한 후보들임
• 너비는 줄어들어도 기준 h가 커질수 있게 짧은 길이의 포인트를 옮겨야함

public int maxArea2(int[] height) {

        int inputLength=height.length;
        int maxProduct=0;

        for (int i = 0; i < inputLength; i++) {

            for (int j = i + 1; j < inputLength; j++) {
                int h = height[i] > height[j] ? height[j] : height[i];
                int subProduct = h * (j - i);
                if (subProduct > maxProduct) {
                    maxProduct = subProduct;
                }
            }
        }
        return maxProduct;
    }