[LeetCode] 11. Container With Most Water - Java

https://leetcode.com/problems/container-with-most-water/description/

Container With Most Water - LeetCode

---

문제

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.

Example 2:

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

 

Constraints:

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

---

풀이

풀이 과정

각 인덱스별 높이를 가진 배열 height가 있고 이 중 두 지점을 선택하여 x축으로 선을 그어 사각형을 만들었을 때 그 최대 넓이를 구하는 문제이다

사각형의 넓이는 두 점의 길이와 두 점의 높이 중 낮은 값에 의해 결정이 된다. 따라서 양 끝 점에서 부터 탐색을 시작하여 높이가 낮은쪽의 인덱스를 하나씩 옮기며 탐색한다.

우선 탐색을 시작할 left와 right인덱스를 양 끝점으로 지정하고 두 지점에서 만들어지는 사각형의 넓이를 구하여 최대 면적값을 초기화 한다.

// 양 끝점에서 시작
int left = 0;
int right = height.length - 1;
// 최대 면적
int maxArea = (right - left) * Math.min(height[left], height[right]);

 

다음으로 left와 right 값이 교차할 때 까지 반복하며
left의 높이값이 right의 높이값 이하라면 left값을 증가, 반대의 경우 right값을 감소시킨다.
이 때 새로 구한 사각형의 넓이가 최대값이 된다면 최대값을 갱신해준다.

// 양 끝점이 교차할 때까지 반복
while(left < right) {
    // left와 right의 높이 중 낮은쪽의 인덱스를 이동
    if(height[left] <= height[right]) {
        left ++;
    } else {
        right--;
    }

    // 새로 구한 넓이가 최대라면 최대값 갱신
    area = (right - left) * Math.min(height[left], height[right]);
    if(area > maxArea) maxArea = area;
}

---

최종 코드

class Solution {
    public int maxArea(int[] height) {
        // 양 끝점에서 시작
        int left = 0;
        int right = height.length - 1;
        // 최대 면적
        int maxArea = (right - left) * Math.min(height[left], height[right]);
        // 현재 탐색 면적
        int area = 0;
        
        // 양 끝점이 교차할 때까지 반복
        while(left < right) {
            // left와 right의 높이 중 낮은쪽의 인덱스를 이동
            if(height[left] <= height[right]) {
                left ++;
            } else {
                right--;
            }
            
            // 새로 구한 넓이가 최대라면 최대값 갱신
            area = (right - left) * Math.min(height[left], height[right]);
            if(area > maxArea) maxArea = area;
        }

        return maxArea;
    }
}

---