[LeetCode] 11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150 

Container With Most Water - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Medium

 

문제

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

수직 높이가 들어있는 배열 height가 있습니다.

물을 최대로 받을 수 있도록 두 높이를 골라서 얻는 최대의 물 양을 구하시오.

 

풀이

투 포인터를 이용한다.

왼쪽 끝과 오른 쪽 끝을 가리키는 변수를 만들고, 왼쪽이 오른쪽보다 커지기 전까지 아래를 반복한다:

현재 두 선으로 얻을 수 있는 양을 구하고, 최댓값을 저장하는 변수에 업데이트한다.

왼쪽의 높이가 작거나같으면 왼쪽 인덱스를 오른쪽으로 이동하고,

그게 아니라면 오른쪽 인덱스를 왼쪽으로 이동한다.

 

다 돌고나서 최댓값을 반환한다. 이 로직은 선형 시간복잡도(O(n))을 가진다. (주어진 요소를 한 번만 탐색하므로)

 

코드

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        const int n = height.size();
        int left = 0, right = n-1;
        int maxAmount = 0;

        while(left < right) {
            int cupHeight = min(height[left], height[right]);
            maxAmount = max(maxAmount, (right - left) * cupHeight);
            if(height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxAmount;
    }
};

 

Python3

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left, right = 0, n-1
        maxAmount = 0

        while left <= right:
            cupHeight = min(height[left], height[right])
            maxAmount = max(maxAmount, (right - left) * cupHeight)

            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return maxAmount

 

Dart

class Solution {
  int maxArea(List<int> height) {
    int n = height.length;
    int left = 0, right = n-1;
    int maxAmount = 0;

    while(left <= right) {
      int cupHeight = min(height[left], height[right]);
      maxAmount = max(maxAmount, (right-left) * cupHeight);

      if(height[left] <= height[right]) {
        left++;
      } else {
        right--;
      }
    }
    return maxAmount;
  }
}

 

Java

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0, right = n-1;
        int maxAmount = 0;

        while(left <= right) {
            int cupHeight = Math.min(height[left], height[right]);
            maxAmount = Math.max(maxAmount, (right-left) * cupHeight);

            if(height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxAmount;
    }
}

 

Swift

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        let n = height.count
        var left = 0, right = n - 1
        var maxAmount = 0

        while left < right {
            let cupHeight = min(height[left], height[right])
            maxAmount = max(maxAmount, (right - left) * cupHeight)
            if height[left] <= height[right] {
                left += 1
            } else {
                right -= 1
            }
        }

        return maxAmount
    }
}