LeetCode - Container With Most Water

Container With Most Water - LeetCode

 

나의 풀이

public class Solution_ContainerWithMostWater {
	public int maxArea(int[] height) {
		int left = 0;
		int right = height.length - 1;
		int answer = calculateArea(height, left, right);
		while (left < right) {
			if (height[left] < height[right]) {
				left++;
			} else {
				right--;
			}
			answer = Math.max(answer, calculateArea(height, left, right));
		}
		return answer;
	}

	private int calculateArea(int[] height, int left, int right) {
		return (right - left) * Math.min(height[left], height[right]);
	}
}

 

 

떠올린 방법

1. 투포인터

- time complexity : O(n)

- space complexity : O(1)

 

++ if, else 문에서 이전의 height보다 옮긴 height가 높아질 때까지 계속 인덱스를 옮기게 할 수도 있다

while 구문안의 if 구문안의 while 구문이 되므로 메서드 추출이 적절히 필요하겠지만 중간으로 갈 수록 이전의 높이보다 작은 것들이 빈번하게 나온다면 calculateArea 메서드를 타지 않으므로 성능이 좋아질 수 있다

다만, 중앙으로 갈수록 점점 높이가 큰 것들이 나오는 경우에는 오히려 성능이 나빠질 것으로 예상된다

 

 

 

결과

 

---

솔루션

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

나와 동일한 풀이이다