C++ 11. Container With Most Water(Leet Code)

Leet Code_11. Container With Most Water

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

각 라인 사이에서 물을 최대로 담을수 있는 수조의 크기

​

방법

1. 각 라인 사이에서 물을 최대로 담을수 있는 수조의 크기

 

 

결과

각 라인 사이에서 물을 최대로 담을수 있는 수조의 크기

 

Test Case는 다 통과했지만 시간 초과된 코드

class Solution {
public:
    int maxArea(vector<int>& height) {
        int nMax = 0;
    int nSize = height.size();
    for(int i = 0 ; i < nSize ; i++)
    {
        for(int j = i+1 ; j <= nSize-1 ; j++)
        {
            int nSum = min(height[i], height[j])*(j-i);
            if(nSum > nMax)
            {
                nMax = nSum;
            }
        }
    }
    return nMax;
    }
};

기존의 모든 라인을 돌면서 가장 큰 수조의 크기를 리턴하는 코드.

테스트 케이스에 대한 답은 나오지만 시간초과가 되었다

이후로 다시 코딩 중..

 

통과한 코드

class Solution {
public:
    int maxArea(vector<int>& height) {
    int nMax = 0;
    int nLeft = 0;
    int nRight = height.size()-1;
    while(nLeft < nRight)
    {
        if(height[nLeft] < height[nRight])
        {
            nMax = height[nLeft]*(nRight-nLeft) > nMax ?  height[nLeft]*(nRight-nLeft) : nMax;
            nLeft++;
        }
        else
            {
                nMax = height[nRight]*(nRight-nLeft) > nMax ? height[nRight]*(nRight-nLeft) : nMax;
                nRight--;
            }
    }
    return nMax;
}
};

양쪽에서 접근하여 접근 횟수를 줄였더니 통과