[Swift LeetCode]11. Container Wi

题目

原题链接
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.

思路

首先请画一个坐标系，横坐标x，分别为0，1，2，3，4...(即题中所说的 i )，而其对应的j为（a1, a2, ..., an）。试想在(i, ai) 和 (i, 0)两点之间做线，

Image001.png

图中红色为随意取的aj值，红色线段就像两个隔板，与x轴合成了一个容器用来装水，图中左侧线段明显比最右侧线段短上一截，因此我们只能取较短的一截作为容器的高度，乘上两条线段之间距离，即min(aj,ai) *（j-i）。

代码是从给定的两端开始遍历，获得此时的容量值作为最大值；接着考虑是最左侧隔板向右移动一位呢还是最右侧隔板向左移一位，这取决于两个隔板的高度，显然我们希望隔板越高越好，这样容器能够容纳的水也越多。因此如果左侧隔板低于最右侧，那么我们淘汰最左侧的隔板，选择left++;反之亦然。

这里给出个极端的示意图，有助于理解：

image2.png

显然2比1的面积大的多。 图比较丑 见谅！

代码

附上swift 版本：

class Solution {
    func maxArea(height: [Int]) -> Int {
                // 容量
        var volume = 0
        // 记录数组左边索引和右边索引
        var left = 0 , right = height.count - 1
        
        while(left < right){
            // 计算一次容量
            let water = min(height[left], height[right]) * (right - left)
            // 比较 获得最大值
            volume = (water > volume) ? (water) : (volume)
            
            if( height[left] < height[right] ){
                left++;
            }else{
                right--;
            }
        }
        return volume
    }
}