URL

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/?envType=daily-question&envId=2024-08-12

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202408/kth_largest_element_in_a_stream/main.fsx

#r "nuget:FSharpx.Collections"
open FSharpx.Collections

type KthLargest =
    { q: IPriorityQueue<int>
      len: int
      k: int }

    static member init (k: int) (nums: int list) : KthLargest =
        nums
        |> List.fold
            (fun acc n -> snd (KthLargest.add n acc))
            ({ q = PriorityQueue.empty false
               len = 0
               k = k })

    static member add (n: int) (k: KthLargest) : (int * KthLargest) =
        if k.len < k.k then
            let q = PriorityQueue.insert n k.q
            PriorityQueue.peek q, { k with q = q; len = k.len + 1 }
        else if PriorityQueue.peek k.q > n then
            PriorityQueue.peek k.q, k
        else
            let _, q = PriorityQueue.pop k.q
            let q = PriorityQueue.insert n q
            PriorityQueue.peek q, { k with q = q }