11. 盛最多水的容器
2022-07-26 本文已影响0人
邦_
最容易想到的暴力法。。 时间复杂度是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
}
