[Leetcode 11] 容器装最多水 一个独立解法

综合讨论区
1

花了我一整天…望指正！
题目：

核心思路：
最高票价最先入场，入场后券值无意义。场内，面积仅由坐标跨度与最新入场价决定，每次入场更新面积，输出历史最高分。

function LeetCode11(height::Vector{Int64})
    indMax = []
    s = 0
    (hval,ind) = findmax(height)
    push!(indMax,ind)
    height[ind[1]] = 0
    for i in 2:length(height)
        (hval,ind) = findmax(height)
        height[ind] = 0
        push!(indMax,ind)
        s0 = (maximum(indMax)-minimum(indMax))*hval
        if s0>=s
            s=s0
        end
    end
    s
end

LeetCode11([1,7,111,139,70,4,8,3,30])
2

由于maximum和minimum，你的算法的复杂度为 O(n^2) 。
直接改进的话可用indMax = DataStructures.SortedSet{Int}()代替indMax = Int[](这里用Int[]取代[]保持类型稳定性)，复杂度降为 O(n\log{n}) 。

标准的做法是用双指针，复杂度 O(n) ：

代码 
 
function max_area(height::Vector{Int})
    i, j = 1, length(height)
    maxa = 0
    while i < j
        if height[i] > height[j]
            maxa = max(maxa, height[j] * (j - i))
            j -= 1
        else
            maxa = max(maxa, height[i] * (j - i))
            i += 1
        end
    end
    return maxa
end
1 个赞
3

如果

height::Vector{Float64}

元素可以不为整数的话，双指针就不对了吧。

4

浮点数也没有问题啊

5

十分感谢！是我一直没能理解双指针：指针每次移动造成的丢弃是严格的。

最后，可以问下这部分相关内容在官方文档的哪一部分吗？搜不到。

6

https://github.com/JuliaCollections/DataStructures.jl

1 个赞