[LeetCode]11. Container With Most Water2️⃣

n의 음이 아닌 정수 a1,a1,,..an이 주어진다. 각각은 coordinate(i,ai) 를 나타내는 것임.

그 ai에서부터 수직선을 내려 긋는다.

가장 많은 물을 담고 있을 수 있는 컨테이너를 생성하는 두 개의 line을 찾아라.

---

---

• 입력 조건
  • line의 개수는, 최대 100000 이다
  • 각 line의 height는 0 이상 10000이하이다.

다시 풀 때 드는 생각

• 만약 모든 두개의 조합을 한다면 → 10만 x 10만 / 2 기 때문에 이렇게 해서는 안 된다.

먼저, 투 포인터로 풀어야 할 것 같다는 생각이 든다.

• container이기 때문에 x * y를 구해야 한다.
• 이 경우, 양 끝의 x에서 시작하여, 좀 더 높은 height를 가진 막대기를 찾는 과정에서, 필연적으로 x가 줄어든다.

일단, 투 포인터를 사용한다면, 포인터를 움직이는 것 자체가, x를 줄이는 과정이 된다.

따라서 무조건, 현재보다 높이가 높아질 수 있는 경우에만 포인터를 움직여야 한다.

• 따라서 min인 line을 변경하도록 포인터를 변경해야 한다.
• 즉, 항상 height는 높이도록 포인터를 움직이는데,
• 이 결과로 계산된 x y 가 기존의 것보다 작다면, 앞으로 더 큰 x y 가 나올 수 없음을 뜻하겠다.

풀이 생각

• container의 좌측 line을 가리키는 left, container의 우측 line을 가리키는 line을 right라고 한다.
• 물의 양은 : ( right- left +1 ) x min(aLeft,aRight)
• 포인팅 하는 두 변수를 두고 있으니 투 포인터가 떠오르긴 하는데....잘 모르겠다. 결국은 두개를 조합하는 모든 경우에 대한 것만 생각난다. 하지만 그렇게 되면
  • n은 최대 10만이다. 만약 투포인터를 사용한다면 50000x50000이 나올 것 같다 즉 2500000000 10억..
• 두개의 조합보다는 , 투포인터를 사용해야 할 것 같지만 잘 모르겠다.

다른 사람의 풀이를 봤다.

• 판단이 필요하다.

  • 현재, h[left]와 h[right]중 더 작은 높이를, 더 크게 만들 수 있는 경우에만 해당 포인터를 움직여 나간다.

  • 왜냐하면, 포인터를 움직인다는 것은 , 이미 x축의 길이를 감소시키는 일이기 때문이다. 따라서 높이라도 더 높아지는 경우여야지 더 큰 container일 확률이 생기는 것이다.

  • 따라서 투 포인터 문제였던 것이다.

    투포인터의 시간 복잡도 : O(n)

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, c = 0, max = 0;
        // n은 2 이상
        while(left<right){
            c = Math.min(height[left],height[right])*(right-left);
            max = Math.max(c,max);
            // left or right를 움직인다 
            if(height[left] < height[right]) left++;
            else{
                right--;
            }
        }
        return max; 
    }
}

더 좋은 풀이

• 즉 , left의 높이가 더 짧은 경우, left는 h[left]보다 더 높은 left 우측의 index인 cleft를 찾는다.
  • 무조건 left에 cleft을 assign할 것이고 cleft은 left+1부터 시작하니 무한루프를 돌 일은 없다.
  • 또한 목표하는 것을 찾으면 break한다.

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, c = 0, max = 0;
        // h[left]<h[right]인 경우, h[left]보다 큰 첫 번째 위치를 찾기 위해 사용할 cleft
        // h[left]>h[right]인 경우, h[right]보다 큰 첫 번째 위치를 찾기 위해 사용할 cright

        int cleft = left, cright = right; 
        // n은 2 이상
        while(left<right){
            c = Math.min(height[left],height[right])*(right-left);
            max = Math.max(c,max);
            // left or right를 움직인다 
            if(height[left] < height[right]) {
                // height[left]보다 큰 height가 첫 번째로 등장하는 곳을 cleft로 찾는다. 
                cleft = left+1; 
                while(cleft<right){
                    if(height[cleft]<=height[left]) cleft++;
                    else break;                     
                }
                left = cleft; 
            }
            else{
                cright = right-1; 
                while(left < cright){
                    if(height[cright] <= height[right] )cright--;
                    else break;
                }
                right = cright;
            }
        }
        return max; 
    }
}