[LeetCode] Container With Most Water (Java)

문제

문제풀이 과정

그리디하게 풀기엔 범위가 커서 시간초과가 날 게 분명하여 투 포인터를 이용하기로

앞쪽을 가리키는 포인터 하나와 뒤를 가리키는 포인터를 하나씩 가지고,

자기보다 큰 높이를 가진 벽을 만났을 때만 넓이를 다시 구하고 max값을 찾도록 했다.

(자기보다 작은 높이를 가진 벽은 계산하나마나 넓이도 작을 것이므로)

class Solution {
    public int maxArea(int[] height) {
        int st = 0;                 // start index
        int ed = height.length - 1; // end index
        
        int leftLen = height[st];   // current left length
        int rightLen = height[ed];  // current right length

        int maxValue = (ed - st) * Math.min(leftLen, rightLen);

        while(st < ed) {
            
            if  (height[st] > leftLen || height[ed] > rightLen) {
                leftLen = height[st];
                rightLen = height[ed];
                maxValue = Math.max(maxValue, (ed - st) * Math.min(leftLen, rightLen));
            }

            if (leftLen >= rightLen) {
                ed--;
            } else {
                st++;
            }
        }

        return maxValue;
    }
}