11. 盛最多水的容器

最容易想到的暴力法。。 时间复杂度是o(n²) 提交后就会发现。超时。。有个很长的测试用例

func maxArea(_ height: [Int]) -> Int {

        let len = height.count
        var maxValue = 0
        for i in  0..<len - 1 {
            
            for j in i+1..<len {
                maxValue = max(maxValue, (j - i) * min(height[i], height[j]))
                
            }
        }

       return maxValue
    
    }

然后左右指针 原理啊= =。。 就是 当一遍的值比较小的时候。。 最大的值 只会在较小的一端收缩后得到
时间上虽然是o(n)级别了。。 但是依旧有很多没有用的组合需要过滤

func maxArea(_ height: [Int]) -> Int {

        let len = height.count
        var maxValue = 0 , l = 0 ,r = len - 1
        
        while l < r {
            
            let leftValue = height[l]
            let rightValue = height[r]
        
            if leftValue < rightValue {
                maxValue = max(maxValue, (r - l) * leftValue)
                l += 1
                
                
            }else {
                maxValue = max(maxValue, (r - l) * rightValue)
                r -= 1
            }

        }

       return maxValue
    
    
    }

优化版本

func maxArea(_ height: [Int]) -> Int {

        let len = height.count
        var maxValue = 0 , l = 0 ,r = len - 1
        
        while l < r {
            
            let leftValue = height[l]
            let rightValue = height[r]
        
            if leftValue < rightValue {
                maxValue = max(maxValue, (r - l) * leftValue)
                while (l < r && leftValue >= height[l]) {
                    l += 1
                }
                
                
            }else {
                maxValue = max(maxValue, (r - l) * rightValue)
                while (l < r && height[r] <= rightValue) {
                    r -= 1
                }
            }

        }

       return maxValue
    
    
    }