[LeetCode] 11. Container With Most Water (C++)

문제

높이와 길이 N 배열이 주어질 때 가장 많은 물을 담을 수 있는 경우

생각할 것

모든 경우를 모두 탐색하거나 투포인터를 써야할 것 같다.

하지만 문제의 조건으로 주어진 배열의 최대 길이가 매우 길기 때문에 모든 경우를 탐색하면 시간초과가 날 것이다!

코드 - 브루트포스

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0, tmp = 0;
        for(int i=0; i<height.size(); i++){ // i : start, j : end
            for(int j=i+1; j<height.size(); j++){
                tmp = height[i] < height[j] ? height[i] : height[j];
                tmp *= j - i;
                if(max < tmp){
                    max = tmp;
                }
            }
        }
        
        return max;
    }
};

예상대로 시간 초과가 발생한다! O(N^2)

결과 코드 - 투 포인터

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int start = 0;
        int end = height.size() - 1;

        for(int i=0; i<height.size(); i++){
            if(start > end) break;
            if(height[start] < height[end]) {
                res = max(res, height[start] * (end - start));
                start++;
            }
            else {
                res = max(res, height[end] * (end - start));
                end--;
            }
        }

        return res;
    }
};

오른쪽과 왼쪽에 포인터를 두고 높이가 작을 경우 중앙으로 이동하면서 최대 값을 찾는 코드이다.

시간복잡도가 O(N)이다.