Sliding window average excluding the k largest

Implement windowed_averages(nums, window_size, k).

Slide a window of window_size consecutive elements across the integer array nums, from left to right. For each full window, drop the k largest values in it and return the average of the remaining window_size - k values. Return one float per window, in order.

• Duplicate values count separately. If a window holds three equal maximums and k = 2, only two of them are dropped.
• 0 <= k < window_size.
• If len(nums) < window_size, return an empty list.
• 1 <= window_size <= len(nums) <= 10^5. Values can be negative.

Aim for better than sorting every window.

Example 1

nums = [4, 9, 1, 7, 3, 8], window_size = 3, k = 1
-> [2.5, 4.0, 2.0, 5.0]

The windows are [4, 9, 1], [9, 1, 7], [1, 7, 3] and [7, 3, 8]. Dropping 9, 9, 7 and 8 leaves (4+1)/2, (1+7)/2, (1+3)/2 and (7+3)/2.

Example 2

nums = [5, 5, 5, 2], window_size = 3, k = 2
-> [5.0, 2.0]

In [5, 5, 5] two 5s are dropped and one remains. In [5, 5, 2] both 5s are dropped.