11. 盛最多水的容器(Swift版)

一、题目

给定 n 个非负整数 a₁，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

二、解题

方法一：

暴力法，通过两次遍历，查找最大容器，时间复杂度为O(n^2),空间复杂度O(1)，但是太过耗时，就不写解法了。

方法二：

使用两个指针，分别设置在头部和尾部，然后循环向中间移动，计算两个指针之间容器的大小，向大的方向移动即可。

如下图，
let list = [1,8,6,2,5,4,8,3,7]
第一次：
var i = 0
var j = list.count - 1  // j = 8
var left = list[i]      // left = 1
var right = list[j]     // right = 7
var area = (j - i) * min(left,right) // area = 8
此时，left较小，则从下图[0-8]可以看出，
[0-7]、[0-6]、[0-5]、[0-4]、[0-3]、[0-2]、[0-1]
的面积都会比[0-8]小(高度已经固定为left，right向left靠拢，宽度必然会减少)，
所以不要在比较这些，需要left向右移动。

第二次：
i = 1;j = 8;left = 8;right = 7;area = (8 - 1) * min(left,right) // area = 49
此时，right较小，则从下图[1-8]可以看出，[2-8]、[3-8]、[4-8]、[5-8]、[6-8]、[7-8]的面积都会比[1-8]小，所以right向左移动。
同时比较第一次和第二次的area，记录最大的area。

后面的依次类推，直到i<=j为止。
具体步骤下下图：

数组[1,,8,6,2,5,4,8,3,7]的计算步骤
LeetCode官方题解图

三、代码实现

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

Demo地址：github