[LeetCode] 11. Container With Most Water

[LeetCode] 11. Container With Most Water

 

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

 

 

문제 풀이

 

접근법

• 투포인터 활용
  • 투포인터 접근법은 가장 높은걸 기준으로 가장 멀리 있는것 부터 하나씩 체크해가는 로직
  • 왜냐하면 가장 멀리 있는 기둥일수록 가장 면적이 크게 잡히기 때문.
  • 면적을 계산한 후 두 기둥 중 더 높은 기둥을 기준 포인터로 남기고 기준 포인터에서 L, R을 옮겨가면서 판단하기
  • 이게 가능한 이유는 `거리`가 가중값 없이 존재하기 때문에 거리를 기반으로 L, R을 옮기면서 찾아보면 된다.
  • 만약 가중값이 존재한다면 그래프 알고리즘으로 바뀌는 문제

 

class Solution_11 {
    func maxArea(_ height: [Int]) -> Int {
        var maxArea = 0
        var left = 0
        var right = height.count - 1
        
        while left < right {
            let distance = right - left
            let area = distance * min(height[left], height[right])
            
            maxArea = max(maxArea, area)
            
            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }
        
        return maxArea
    }
}

 

논리 이미지