[LeetCode] 11. Container With Most Water / Swift

[문제 보기]

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1] Output: 1

Example 3:

Input: height = [4,3,2,1,4] Output: 16

Example 4:

Input: height = [1,2,1] Output: 2

 

Constraints:

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

 

 

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

Container With Most Water - LeetCode

 

---

처음에 n(n-1)/ 2인 O(n^2)의 brute force로 풀었다가 시간초과가 떴다.

leetcode는 투포인터 문제가 상당히 많은 것 같다.

 

가장 큰 영역을 구하기 위해서는 너비도 커야하고 높이도 커야하지만 여기서 높이는 양 끝 점의 높이 중에서 작은 쪽이 반영이 된다는 것에 잘 생각해 보아야한다.

이 구현 방법으로 정말로 모든 경우의 수를 구하는가에 대해서는,

left와 right는 서로 중앙을 향해서 한칸씩 움직이는데 둘 중 작은 쪽이 움직인다.

어느 한쪽이 연속해서 가장 큰 2개를 지나치지 않으므로 (작은쪽이 먼저 움직이므로) left와 right는 항상 각각 현재 상태보다 높이가 큰 2개를 빠짐없이 지나가게 된다.

이 방법으로 풀었을 때 O(n)의 시간복잡도를 갖는다.

 

 

// 처음 시도 버전 (시간초과)
class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var max = 0
        for i in (0..<height.count - 1) {
            for j in (i + 1..<height.count) {
                var w = j - i
                if w < 0 { w *= -1 }
                var h = min(height[i], height[j])
                
                if max < w * h {
                    max = w * h
                }
            }
        }
        return max
    }
}

// 최종 제출 버전
class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var left = 0, right = height.count - 1
        var maxArea = 0
        while left < right {
            let area = (right - left) * min(height[left], height[right])
            if maxArea < area { maxArea = area }
            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }
        return maxArea
    }
}