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

花了我一整天…望指正!
题目:

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

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])

由于maximumminimum,你的算法的复杂度为 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 个赞

如果

height::Vector{Float64}

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

浮点数也没有问题啊

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

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

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

1 个赞

备案号:京ICP备17009874号-2