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).

转载请注明出处：