LeetCode #11 Container With Most Water

LeetCode #11 Container With Most Water

Question

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution

Approach #1

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

Time complexity: O(n).

Space complexity: O(1).

转载请注明出处：http://www.cnblogs.com/silence-cnblogs/p/6861450.html