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

[전략]
2중 for 문으로 모든 i,j 쌍에 대해 area를 구해본다.

class Solution {

    public int maxArea(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

[전략]

• 가장 바깥에서부터 유망한 case의 area를 구해감
• 양 끝점 중, 짧은 길이의 점을 그대로 두고 긴 길이의 점을 옮길 경우, 더 긴 길이를 만나더라도 h의 기준은 항상 짧은 길이이고 너비만 줄어들 뿐이므로 항상 작아진다.
  => 짧은 길이의 점을 고정하고 반대편의 점만 안쪽으로 이동하였을때는 어떤 케이스도 유망하지 않으므로 짧은 길이의 점을 고정한 케이스는 탐색해볼 필요 없음
  ==> 짧은 길이의 점을 이동

 public int maxArea(int[] height) {

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

        int i = 0;
        int j = inputLength - 1;
        while (i<j) {

           int productBetweenTwo = Math.min(height[i], height[j]) * (j - i);
           maxProduct = Math.max(maxProduct, productBetweenTwo);
           if(height[i]<height[j]){
               i++;
           }else{
               j--;
           }
        }
        return maxProduct;
    }