Today I Learned

오늘은 leetcode로 자바 문제를 풀었다.

11. Container With Most Water

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

문제

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.

ex)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.

풀이과정

• 이 문제는 주어진 배열에서 물을 담을 때 최대로 담을 수 있는 물의 양을 찾는 문제다. 값이 max가 되는 두 값을 배열에서 찾아야 하는 문제이므로 투포인터로 풀어보았다.

1. 최대 영역을 저장할 변수를 초기화하고, 시작과 끝점을 가리킬 두 포인터를 만든다.

2. 왼쪽의 포인터가 오른쪽의 포인터보다 작을 때까지 반복되는 while 반복문을 만든다.

3. 두 포인터중 낮은 높이를 선택하고 거리를 계산해 영역을 구한다.
   현재 영역의 넓이가 최대 영역보다 넓으면 Math.max로 업데이트 한다.

4. 높이가 작은 쪽의 포인터를 안쪽으로 이동시킨다.

5. 반복문이 마무리 되면 최대 영역이 반환된다.

Java 코드

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int w = right - left;
            int area = h * w;
            maxArea = Math.max(maxArea, area);
            
            if (height[left] < height[right]) left++;
            else right--;
        }
        
        return maxArea;
    }
}